Kürzester Weg (AB)
Problem
Sie erhalten eine Beschreibung des Straßennetzes des Landes. Ihre Aufgabe ist es, die Länge des kürzesten Weges zwischen den Städten A und B zu finden.
Eingabe
Das Straßennetz ist in der Eingabedatei wie folgt definiert: Die erste Zeile enthält die Zahlen N und K (1<=N<=100000, 0<=K<=300000), wobei K – die Anzahl der Straßen ist. Jede der folgenden K-Zeilen enthält eine Beschreibung der Einbahnstraße – drei ganze Zahlen ai, bi und li (1aibiN, 1li106). Dies bedeutet, dass es eine Straße der Länge li gibt, die von der Stadt ai in die Stadt bi führt. Die letzte Zeile enthält die beiden Zahlen Aund B und die Nummern der Städte, zwischen denen die kürzeste Entfernung berechnet werden soll (1<=A,B<=N )
Ausgabe
Sie müssen eine einzelne Zahl in die Ausgabedatei ausgeben. – die Entfernung zwischen den gewünschten Städten. Wenn es nicht möglich ist, von Stadt A nach Stadt B zu gelangen, ziehen Sie –1 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1 |
115 |