Solução Informática – Nível Intermediário – Semana 32

Escrito por Estela Baron

Conhecimento prévio necessário:

• Algoritmo de Dijkstra

Nesse problema, a primeira ideia que temos é tentar realizar um algoritmo de dijkstra para obter o menor custo do vértice $1$ até o vértice $C$, pois o nosso grafo é bidirecionado e as arestas têm peso. No entanto, a condição imposta impede o funcionamento da ideia original, pois o menor custo pode ser com uma quantidade ímpar de pedágios.

Para resolver isso, em vez de armazenar o menor custo para chegar em um determinado vértice, vamos armazenar dois custos: $custo[0][i]$: o menor valor para chegar em $i$ com um número par de pedágios e $custo[1][i]$: o menor valor com um número ímpar de pedágios.

Com isso, podemos realizar o algoritmo de dijkstra com algumas alterações:

• a $priority\_queue$ armazena primeiro o $custo$ (para ordenar de forma crescente), depois o vértice e, por último, a paridade (os dois últimos não precisam estar em uma ordem específica)
• quando for visitar um vizinho, tem que inverter a paridade atual – um jeito de fazer isso é fazer a operação XOR (^) , pois $1 \wedge1 = 0 \;e\; 0 \wedge 1 = 1$
• o único custo inicial que temos é o $custo[0][1] = 0$, pois, inicialmente, Pat já começa no vértice $1$ com zero de custo e zero pedágios (quantidade par)
• tem que retornar $custo[0][C]$ ($custo[1][C]$ não atende às condições), caso contrário, $-1$

A complexidade dessa solução é a mesma de um algoritmo de dijkstra normal, ou seja, $O(V\;.\; log\;C)$

Recomendamos que você tente implementar o problema antes de ver o código.Veja a implementação nesse link.