Sconto singolo
Alex vive nella città
1 e desidera raggiungere la città n. Vuole trovare il percorso aereo dal costo minimo, sfruttando la possibilità di utilizzare un coupon sconto. Questo coupon si può usare una sola volta per dimezzare il prezzo di un singolo volo lungo il tragitto. Se lo si applica a un volo con prezzo x, il nuovo prezzo diventa .
Trova il costo del percorso più economico dalla città 1 alla città n.Input
La prima riga contiene due numeri interi separati da uno spazio,
n e m (), che indicano rispettivamente il numero di città e il numero di voli.Le successive
m righe descrivono i voli. Ogni riga contiene tre numeri interi separati da uno spazio, a, b e (), che rappresentano un volo bidirezionale dalla città a alla città b con prezzo .Output
Stampa un singolo intero che indica il costo del percorso più economico dalla città
1 alla città n.Esempi
Ingresso | Uscita |
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