Encontre o Caminho Mais Curto 4
É-lhe fornecido um mapa formado por
n cidades e m estradas bidirecionais que ligam essas cidades. Cada estrada tem um comprimento inteiro não negativo, indicado por . O teu objetivo é encontrar o caminho mais curto entre a cidade 1 e a cidade n.💡
Nota que, nesta tarefa, é preciso encontrar tanto o comprimento do caminho mais curto quanto o próprio caminho.
Entrada
A primeira linha contém dois inteiros separados por espaço,
n e m (), que representam o número de cidades e o número de estradas, respetivamente.As próximas
m linhas contêm cada uma três inteiros separados por espaço, , e , que representam uma estrada entre as cidades e com comprimento ().Saída
Dois inteiros,
k e l, separados por um espaço. Aqui, k representa o número de cidades no caminho mais curto e l representa o comprimento desse caminho.Na linha seguinte, imprime
k inteiros separados por espaço, representando as cidades que compõem o caminho mais curto.No caso de existirem vários caminhos mais curtos, podes apresentar qualquer um deles. Repara também que não é necessário minimizar o valor de
k.Exemplos
Entrada | Saída |
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