Escrito por Estela Baron
Conhecimento prévio necessário:
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.