Viagem do Flúcio
Existem vários algoritmos conhecidos para encontrar o menor caminho de um local para o outro. Temos GPS em nossos carros e em nossos celulares para nos mostrar o caminho mais rápido para onde nós quisermos ir. Flúcio gosta de viajar lentamente pois gosta de apreciar a estrada enquanto come um delicioso pão. Ajude Flúcio à encontrar o maior caminho entre a sua cidade e a de destino sem passar por uma cidade mais de uma vez.
Um caminho consiste em uma sequência de cidades distintas , tais que existe uma rota de para para todo .
Entrada
A primeira linha da entrada contém dois inteiros o número de cidades e o número de estradas conectando as cidades. Existe no máximo uma estrada entre qualquer par de cidades. As cidades são numeradas de à , sendo a cidade de Flúcio e a cidade de destino.
As próximas linhas contém cada uma três inteiros indicando uma estrada entre as cidades e de tamanho km. Cada estrada possuí mão dupla. Sempre existe um caminho de à .
Saída
Seu código deve imprimir um único inteiro, o tamanho do maior caminho que começa na cidade , termina na cidade , e não visita qualquer cidade mais de uma vez. O tamanho do caminho é a soma dos tamanhos das estradas no caminho.
ENTRADA | SAÍDA |
3 3 0 2 5 0 1 4 1 2 3 |
7 |