Find The Shortest Path 4
Vous disposez d’une carte composée de
n villes et de m routes bidirectionnelles reliant ces villes. Chaque route a une longueur entière non négative, notée . Votre objectif est de déterminer le chemin le plus court reliant la ville 1 à la ville n.💡
Notez que pour cette tâche, vous devez trouver à la fois la longueur du plus court chemin et le chemin lui-même.
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 routes.Les
m lignes suivantes contiennent chacune trois entiers séparés par un espace, , et , décrivant une route entre les villes et de longueur ().Sortie
Vous devez d’abord afficher deux entiers,
k et l, séparés par un espace. Ici, k indique le nombre de villes composant le plus court chemin, et l indique la longueur de ce chemin.Sur la ligne suivante, affichez
k entiers séparés par des espaces pour représenter les villes traversées par le plus court chemin.S’il existe plusieurs chemins de même longueur minimale, vous pouvez en donner n’importe lequel. Il n’est pas nécessaire de minimiser la valeur de
k.Exemples
Entrée | Sortie |
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