1 - k BFS
Problem
Es wurde ein orientiertes gewichtetes Diagramm angegeben. Sie müssen den Abstand vom 1 -Scheitelpunkt zu allen anderen finden, indem Sie den 1 - k BFS -Algorithmus verwenden.
Eingabe
Die erste Zeile enthält 2 ganze Zahlen n und m, jeweils die Anzahl der Scheitelpunkte und Kanten im Diagramm. In den folgenden m Zeilen werden drei Zahlen angegeben: a und b - die Eckpunkte, die die Kante verbinden, und c - das Gewicht dieser Kante (a, b, c >= 0).
Ausgabe
Wenn es keinen möglichen Pfad von 1 zu i gibt, muss Impossible ausgegeben werden.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
1 4 3 6 4 Impossible Impossible Impossible
|