Solução Mania de Par

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Este problema é uma adaptação muito simples do algoritmo de Dijkstra. Basta guardarmos não só a menor distância para uma determinada cidade, mas a menor distância passando por um número par de pedágios e a menor passando por um número ímpar.

Seja $$dist[v]$$ um par de inteiros cujo primeiro elemento é a menor distância da origem a $$v$$ que passa por um número par de pedágios e o segundo, por um número ímpar. Agora, para executarmos o Dijkstra, basta fazermos dois tipos de atualização. Suponha que estamos na cidade $$v$$ olhando o vizinho $$u$$, cuja distância é $$d$$. Para atualizarmos a distância ímpar de $$u$$, verificamos de $$d+dist[v].F<dist[u].S$$, pois $$dist[v].F$$ passa por um número par de pedágios, logo, ao passarmos pela estrada $$v – u$$, adicionamos um pedágio e agora temos um número ímpar. Atualizamos o número par de maneira análoga.

No fim, basta imprimirmos a resposta, que está salva na distância par ao destino. Segue o código para melhor entendimento.

https://gist.github.com/rogerioagjr/7b310ec398c1094bf5173e4bcea0fd4a