Dijkstra : Récupération de chemin
Problem
On vous donne un graphique pondéré orienté. Trouver le chemin le plus court d'un sommet donné à un autre.
Entrée
La première ligne contient trois nombres : N, S et F (1≤N≤100, 1≤S, F≤N), où N &ndash ; nombre de sommets du graphe, S – sommet initial, et F – final. Dans les N lignes suivantes, entrez N nombres chacun, n'excédant pas 100, – matrice d'adjacence graphique, où -1 signifie qu'il n'y a pas d'arête entre les sommets et tout nombre non négatif – la présence d'une arête de poids donné. Des zéros sont écrits sur la diagonale principale de la matrice.
Sortie
Il est nécessaire d'afficher séquentiellement tous les sommets d'un (n'importe lequel) des chemins les plus courts, ou un nombre -1 s'il n'y a pas de chemin entre les sommets spécifiés.
Exemples
| # |
Entrée |
Sortie |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
2 3 1 |