Encuentra la ruta más corta 4
Se te proporciona un mapa compuesto por
n ciudades y m carreteras bidireccionales que las conectan. Cada carretera tiene una longitud entera no negativa indicada por . Tu tarea es encontrar la ruta más corta entre la ciudad 1 y la ciudad n.💡
Ten en cuenta que, en esta tarea, debes hallar tanto la longitud de la ruta más corta como la propia ruta.
Entrada
La primera línea contiene dos números enteros separados por espacio,
n y m (), que representan la cantidad de ciudades y la cantidad de carreteras, respectivamente.Las siguientes
m líneas contienen, cada una, tres números enteros separados por espacio: , y , que describen una carretera entre las ciudades y con longitud ().Salida
Debes mostrar dos números,
k y l, separados por un espacio. Aquí, k indica la cantidad de ciudades en la ruta más corta, y l representa la longitud de dicha ruta.En la siguiente línea, muestra
k números separados por espacio que representen las ciudades que conforman la ruta más corta.En caso de haber múltiples rutas más cortas, puedes imprimir cualquiera de ellas. Además, no es necesario minimizar el valor de
k.Ejemplos
Entrada | Salida |
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