Solução Desvio de Rota

Solução por Rogério Júnior

A solução o problema é uma única chamada do algoritmo de Dijkstra. Se você não o conhece, clique aqui para acessar nossa aula de menor caminho em grafos. Entretanto, há um diferencial no problema: existem algumas cidades que pertecem a uma rota e se o caminhão passar por elas, não pode sair desta rota. Este pequeno problema pode ser corrigido diretamente na leitura da entrada: basta ignorarmos todas as estradas que partem de uma cidade que pertence à rota para uma que não pertence a ela, pois não poderemos usá-las para encontrar o menor caminho! Assim, basta lermos a entrada ignorando as estrada inúteis e depois aplicarmos o algoritmo de Dijkstra! Segue o código para melhor entendimento:

https://gist.github.com/rogerioagjr/d559e10f332c662e1915