Feito por Thiago Mota
Imagine o seguinte problema, um robô quer chegar em uma estação, ele pode andar por dois tipos de trilhos, os trilhos passivos são induzidos e não consome energia quando o robô anda por ela, já os trilhos ativos consomem $$1$$ de energia, dado $$N$$ estações e $$M$$ trilhos diga a menor quantidade de energia para o robô sair da estação $$1$$ e chegar em $$N$$.
Nesse problema podemos imaginar um grafo com arestas de peso $$0$$ e $$1$$:
A solução em $$O((n+m) \log n)$$ seria utilizando o algoritmo de Dijkstra:
https://gist.github.com/Thiago4532/7c1a7e4baae70df1e88b42e62ab1a993
A ideia de hoje é utilizar BFS 0-1, a ideia é similar ao Dijkstra mas como possuímos apenas dois valores, não precisamos utilizar uma priority_queue, pois podemos apenas sempre tentar ir na aresta que possuí menor valor, exatamente na mesma ideia do Dijkstra mas utilizando uma deque, onde os valores de $$0$$ sempre serão inseridos na frente da deque e os $$1$$ atrás, dando sempre prioridade aos $0$’s, isso deixará a complexidade do código em $$O(n+m)$$. Segue o código comentado:
https://gist.github.com/Thiago4532/4cbaaf70d8b01c1769df084ff969be75