Escrito por Caique Paiva
Conhecimento prévio necessário:
Vamos fazer dois Dijkstra, e eles vão funcionar da seguinte maneira:
- O primeiro Dijkstra vai ser normal, dizendo qual é o menor caminho de $$1$$ para $$i$$.
- O segundo Dijkstra vai dizer qual é o menor caminho de $$1$$ para $$i$$ usando um cupom.
Para o primeiro Dijkstra, a transição vai ser o seguinte:
Se estamos no vértice $$u$$ e queremos ir para $$v$$, vemos se a distância de $$1$$ para $$v$$ já calculada é maior que a distância de $$1$$ para $$u$$ mais o peso da aresta de $$u$$ para $$v$$ (Ou seja, se $$dist[v] > dist[u] + w$$). Se for verdade, atualizamos o valor de $$dist[v]$$ e colocamos $$v$$ na priority queue.
Para o segundo Dijkstra, se estamos no vértice $$u$$ e queremos ir para $$v$$, temos duas possibilidades:
- Se já usamos o cupom no caminho de $$1$$ para $$u$$, logo, vemos se a distância de $$1$$ para $$v$$ já calculada é maior que a distância de $$1$$ para $$u$$ mais o peso da aresta de $$u$$ para $$v$$ (Ou seja, se $$dist2[v] > dist2[u] + w$$). Se for verdade, atualizamos o valor de $$dist2[v]$$ e colocamos $$v$$ na priority queue.
- Se ainda não usamos o cupom, vamos usar ele na aresta de $$u$$ para $$v$$, portanto, vemos se a distância de $$1$$ para $$v$$ com cupom já calculada é maior do que a distância sem o cupom de $$1$$ para $$u$$ mais o peso da aresta de $$u$$ para $$v$$ dividido por $$2$$ (Ou seja, se $$dist2[v] > dist[u] + w/2$$). Se for verdade, atualizamos o valor de $$dist2[v]$$ e colocamos $$v$$ na priority queue.
Então primeiro fazemos o primeiro Dijkstra normal, e depois fazemos outro usando as informações do primeiro Dijkstra também, e dai é só retornar a resposta de $$n$$ para o segundo Dijkstra.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.