Remise unique
Alex habite dans la ville
1 et souhaite rejoindre la ville n. Il veut déterminer l'itinéraire de vol le moins cher, en tenant compte d’un coupon de réduction disponible. Ce coupon de réduction ne peut être utilisé qu’une seule fois pour diviser par deux le prix d’un vol pendant le trajet. Lorsqu’il l'emploie pour un vol dont le prix est x, le coût devient .
Trouvez le tarif le plus bas pour aller de la ville 1 à la ville n.Entrée
La première ligne contient deux entiers séparés par un espace,
n et m (), qui représentent respectivement le nombre de villes et le nombre de vols.Les
m lignes suivantes décrivent les vols. Chaque ligne contient trois entiers séparés par un espace a, b et (), indiquant un vol bidirectionnel entre la ville a et la ville b avec un prix de .Sortie
Affichez un unique entier représentant le prix le plus bas pour un trajet de la ville
1 à la ville n.Exemples
Input | Output |
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