Trova Il Percorso Più Breve 4
Ti viene fornita una mappa composta da
n città e m strade bidirezionali che collegano queste città. Ogni strada ha una lunghezza intera non negativa, indicata da . Il tuo compito è trovare il percorso più breve tra la città 1 e la città n.💡
Nota che in questo esercizio devi trovare sia la lunghezza del percorso più breve sia il percorso stesso.
Input
La prima riga contiene due interi separati da spazio,
n e m (), che rappresentano rispettivamente il numero di città e il numero di strade.Le successive
m righe contengono ciascuna tre interi separati da spazio, , , e , che rappresentano una strada tra le città e con lunghezza ().Output
Due interi,
k e l, separati da uno spazio. Dove k rappresenta il numero di città nel percorso più breve, mentre l è la lunghezza di tale percorso.Nella riga successiva, stampa
k interi separati da spazio, corrispondenti alle città che formano il percorso più breve.Nel caso esistano più percorsi di uguale lunghezza, puoi stamparne uno qualunque. Nota anche che non è necessario minimizzare il numero
k.Esempi
Input | Ingresso |
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