Find The Shortest Path 1
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 nicht-negative Länge, bezeichnet durch . Deine Aufgabe besteht darin, die Länge des kürzesten Wegs zwischen Stadt 1 und Stadt n zu ermitteln.Input
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen,
n und m (), die für die Anzahl der Städte bzw. die Anzahl der Straßen stehen.Die nächsten
m Zeilen enthalten jeweils drei durch Leerzeichen getrennte ganze Zahlen , und , die eine Straße zwischen den Städten und mit Länge beschreiben ().Output
Das Programm soll die Länge des kürzesten Wegs von Stadt
1 nach Stadt n ausgeben.Beispiele
Eingabe | Ausgabe |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB