Solução Mania de Par

0 Flares Facebook 0 0 Flares ×

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.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: