Find The Shortest Path 3
Du erhältst eine Karte mit
n Städten und m bidirektionalen Straßen, die diese Städte miteinander verbinden. Jede Straße hat eine nichtnegative ganzzahlige Länge, angegeben durch . Deine Aufgabe ist es, die Länge des kürzesten Wegs zwischen der Stadt 1 und der Stadt n zu bestimmen.Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte Ganzzahlen,
n und m (), welche die Anzahl der Städte bzw. die Anzahl der Straßen angeben.Die nächsten
m Zeilen enthalten jeweils drei durch Leerzeichen getrennte Ganzzahlen , und , die eine Straße zwischen den Städten und mit der Länge beschreiben ().Ausgabe
Gib eine einzige Ganzzahl aus, die die Länge des kürzesten Pfads von Stadt
1 zu Stadt n angibt.Beispiele
Eingabe | Ausgabe |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB