Informática – Nível Intermediário – Semana 32

—

por

Estela Nakamura

Mania de Par

Pat quer viajar para uma outra cidade, mas quer que a quantidade de pedágios pagos seja par. Sabendo que cada estrada é bidirecional e possui um pedágio com um custo G, ajude Pat a descobrir qual é o menor custo que ela terá que pagar para chegar em seu destino obedecendo a condição.

Entrada:

A entrada consiste de diversas linhas.

A primeira linha possui dois inteiros C e V, o número de cidades e a quantidade de estradas, respectivamente. Cada uma das V linhas apresenta 3 inteiros: C_1, C_2, G, indicando que o pedágio entre as cidades C_1 e C_2 tem custo G.

Pat está na cidade 1 e quer chegar na cidade C.

Saída:

O seu programa deve imprimir uma única linha contendo o menor custo para que Pat chegue à cidade C pagando um número par de pedágios. Caso isso não seja possível, imprima -1.

Limites:

  • 2\leq C\leq 10^4
  • 0\leq V\leq 50000
  • 1\leq C_1, C_2\leq C
  • 1\leq G\leq 10^4

Exemplo:

Entrada Saída
4 4
1 2 2
2 3 1
2 4 10
3 4 6		 
12
Entrada Saída
5 6
1 2 3
2 3 5
3 5 2
5 1 8
2 4 1
4 5 4		 
-1

Para submeter a sua solução, use esse link