Dijkstra: Wiederherstellung des Weges
Problem
Es wurde ein orientiertes gewichtetes Diagramm angegeben. Finden Sie den kürzesten Weg von einem bestimmten Eckpunkt zum anderen.
Eingabe
Die erste Zeile enthält drei Zahlen: N, S und F (1≤N≤100, 1≤S, F≤N), wobei N – die Anzahl der Eckpunkte des Graphen, S – der Anfangsscheitelpunkt und F – der Endpunkt ist. In den nächsten N Zeilen werden N Zahlen eingegeben, die nicht größer als 100 sind, – die Adjazenzmatrix des Graphen, wobei -1 bedeutet, dass keine Kante zwischen den Eckpunkten fehlt und jede nicht negative Zahl die Anwesenheit einer Kante dieses Gewichts ist. Auf der Hauptdiagonale der Matrix sind Nullen geschrieben.
Ausgabe
Sie müssen alle Eckpunkte eines (beliebigen) der kürzesten Pfade nacheinander ausgeben, oder eine Zahl -1, wenn kein Pfad zwischen den angegebenen Eckpunkten vorhanden ist.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |