Solução Avançado Infomática – Semana 42

Solução de Frederico Bulhões

Esse problema é um menor caminho em um grafo porém com uma condição a mais: somente podemos avançar de um sinal quando ele estiver verde.

Então para resolver esse problema vamos considerar um menor caminho de Dijkstra, porém quando consideramos colocar uma aresta e ela está vermelha, consideramos apenas o memento imediato quando ela se torna verde novamente.

A partir daí vemos quato tempo leva para partir de um vértice A e chgar num B.

Código para melhor entendimento:

https://gist.github.com/fredbr/2c749c7de0ee4fbd89686218cc1d3d6a