Trouver le chemin le plus court 3
On vous présente une carte composée de
n villes reliées par m routes bidirectionnelles. Chaque route possède une longueur de type entier non négatif, indiquée par . Votre objectif est de calculer la distance du plus court chemin entre la ville 1 et la ville n.Entrée
La première ligne contient deux entiers séparés par un espace,
n et m (), représentant respectivement le nombre de villes et le nombre de routes.Les
m lignes suivantes décrivent chacune une route à l’aide de trois entiers séparés par des espaces : , et , qui indiquent qu’il existe une route entre les villes et de longueur ().Sortie
Affichez un seul entier représentant la longueur du plus court chemin reliant la ville
1 à la ville n.Exemples
Entrée | Sortie |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB