Encontrar o Caminho Mais Curto 2
Dispõe-se de um mapa constituído por
n cidades e m estradas bidirecionais que ligam estas cidades. Cada estrada possui um comprimento inteiro não negativo, denotado por . A sua tarefa é determinar o comprimento do caminho mais curto entre a cidade 1 e a cidade n.Entrada
A primeira linha contém dois inteiros separados por espaço,
n e m (), que representam, respetivamente, o número de cidades e o número de estradas.Nas próximas
m linhas, cada linha contém três inteiros separados por espaço: , e , descrevendo uma estrada entre as cidades e com comprimento ().Saída
Escreva um único inteiro que corresponda ao comprimento do caminho mais curto entre a cidade
1 e a cidade n.Exemplos
Entrada | Saída |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB