Ford-Bellman
Problem
Es ist ein orientierter Graph gegeben, der mehrere Kanten und Schleifen enthalten kann. Jede Kante hat ein Gewicht, das durch eine ganze Zahl ausgedrückt wird (möglicherweise negativ). Es ist garantiert, dass es keine negativen Gewichtszyklen gibt.
Sie müssen die Längen der kürzesten Pfade vom Scheitelpunkt Nummer 1 bis zu allen anderen Scheitelpunkten berechnen.
Eingabe
Das Programm erhält zuerst die Zahl N (1 <= N <= 100) – die Anzahl der Eckpunkte des Graphen und die Anzahl M (0 <= M <= 10000) – die Anzahl der Kanten. In den folgenden Zeilen gibt es M drei Zahlen, die die Kanten beschreiben: den Anfang der Kante, das Ende der Kante und das Gewicht (das Gewicht ist eine ganze Zahl von -100 bis 100).
Ausgabe
Das Programm sollte N Zahlen ausgeben – die Entfernung vom Eckpunkt Nummer 1 zu allen Eckpunkten des Graphen. Wenn kein Pfad zum entsprechenden Scheitelpunkt vorhanden ist, geben Sie anstelle der Pfadlänge die Zahl 30.000 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |