Dijkstra: recupero del percorso
Problem
Ti viene fornito un grafico ponderato diretto. Trova il percorso più breve da un dato vertice a un altro.
Input
La prima riga contiene tre numeri: N, S e F (1≤N≤100, 1≤S, F≤N), dove N – numero di vertici del grafico, S – vertice iniziale e F – finale. Nelle successive N righe, inserisci N numeri ciascuno, non superiore a 100, – grafico matrice di adiacenza, dove -1 significa nessun bordo tra i vertici e qualsiasi numero non negativo – la presenza di un bordo di peso dato. Gli zeri sono scritti sulla diagonale principale della matrice.
Uscita
È necessario visualizzare in sequenza tutti i vertici di uno (qualsiasi) dei percorsi più brevi, o un numero -1 se non esiste alcun percorso tra i vertici specificati.
Esempi
| # |
Input |
Uscita |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |