Find The Shortest Path 4
Sie haben eine Karte, die aus
n Städten und m bidirektionalen Straßen besteht, welche diese Städte miteinander verbinden. Jede Straße hat eine nichtnegative ganzzahlige Länge, die durch angegeben ist. Ihre Aufgabe besteht darin, den kürzesten Pfad zwischen der Stadt 1 und der Stadt n zu finden.💡
Beachten Sie, dass Sie in dieser Aufgabe sowohl die Länge des kürzesten Pfads als auch den Pfad selbst ermitteln müssen.
Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen,
n und m (), die die Anzahl der Städte und die Anzahl der Straßen angeben.Die folgenden
m Zeilen enthalten jeweils drei durch Leerzeichen getrennte ganze Zahlen , und , womit eine Straße zwischen den Städten und mit der Länge beschrieben wird ().Ausgabe
Geben Sie zwei ganze Zahlen,
k und l, getrennt durch ein Leerzeichen aus. Dabei steht k für die Anzahl der Städte im kürzesten Pfad und l für die Länge dieses Pfads.Geben Sie in der nächsten Zeile
k durch Leerzeichen getrennte ganze Zahlen aus, die der Reihenfolge der Städte auf dem kürzesten Pfad entsprechen.Falls mehrere kürzeste Pfade existieren, können Sie jeden beliebigen ausgeben. Es ist außerdem nicht erforderlich,
k zu minimieren.Beispiele
Input | Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 3 6
1 2 4 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 5 MB