Desconto Único
Alex mora na cidade
1 e deseja chegar à cidade n. Ele quer encontrar a rota de voo mais económica, tendo em conta que dispõe de um cupão de desconto. Esse cupão de desconto pode ser usado apenas uma vez, para reduzir para metade o preço de um único voo ao longo do percurso. Quando ele utiliza o cupão num voo cujo preço é x, o custo passa a ser .
Encontre o preço da rota mais barata da cidade 1 até à cidade n.Entrada
A primeira linha contém dois inteiros,
n e m, separados por espaço (), que representam o número de cidades e o número de voos, respetivamente.As próximas
m linhas descrevem os voos. Em cada linha, encontram-se três inteiros, a, b e , separados por espaço (), indicando um voo bidirecional da cidade a para a cidade b, com um preço de .Saída
Imprime um único inteiro, que representa o preço da rota mais barata entre a cidade
1 e a cidade n.Exemplos
Entrada | Saída |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB