Einzelrabatt
Alex lebt in Stadt
1 und möchte Stadt n erreichen. Er möchte die Flugstrecke mit den geringstmöglichen Kosten finden und dabei einen Rabattgutschein nutzen. Dieser Gutschein kann pro Strecke nur ein einziges Mal eingesetzt werden, um den Preis eines einzelnen Flugs zu halbieren. Wird er für einen Flug mit Kosten x verwendet, so wird der Preis auf herabgesetzt.
Finde den Preis der günstigsten Flugverbindung von Stadt 1 nach Stadt n.Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte Ganzzahlen
n und m (). Diese geben jeweils die Anzahl der Städte sowie die Anzahl der Flüge an.Die nächsten
m Zeilen beschreiben die einzelnen Flüge. In jeder dieser Zeilen stehen drei durch Leerzeichen getrennte Ganzzahlen a, b und (). Diese beschreiben einen bidirektionalen Flug von Stadt a nach Stadt b mit einem Preis von .Ausgabe
Gib eine einzelne ganze Zahl aus, die den Preis der günstigsten Verbindung von Stadt
1 nach Stadt n angibt.Beispiele
Eingabe | Ausgabe |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB