Solução Informática - Nível Avançado - Semana 29

Escrito por Caique Paiva

Conhecimento prévio necessário:

• Algoritmo de Dijkstra

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:

1. 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.
2. 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.