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:
| // Ideias 07 – BFS 0-1 | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef pair<int, int> pii; | |
| const int maxn = 1e5 + 10; | |
| vector<pii> grafo[maxn]; | |
| int n, m, dist[maxn]; | |
| void dijkstra(int x) { | |
| memset(dist, 0x3f3f3f3f, sizeof dist); // Inicializando distancia como "infinito" | |
| dist[x] = 0; | |
| fila.push({dist[x], x}); | |
| while (!fila.empty()) { | |
| int u = fila.top().second; | |
| fila.pop(); | |
| for(int i = 0; i < (int)grafo[u].size(); i++) { | |
| int v = grafo[u][i].first; | |
| int d = grafo[u][i].second; | |
| if(dist[v] > dist[u] + d) { | |
| dist[v] = dist[u] + d; | |
| fila.push({dist[v], v}); | |
| } | |
| } | |
| } | |
| } | |
| int main(){ | |
| ios::sync_with_stdio(false), cin.tie(0); | |
| cin >> n >> m; | |
| for(int i=1;i<=m;i++){ | |
| int a, b, c; | |
| cin >> a >> b >> c; | |
| grafo[a].push_back({b, c}); | |
| grafo[b].push_back({a, c}); | |
| } | |
| dijkstra(1); | |
| cout << dist[n] << "\n"; | |
| return 0; | |
| } |
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:
| // Ideias 07 – BFS 0-1 | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef pair<int, int> pii; | |
| const int maxn = 1e5 + 10; | |
| vector<pii> grafo[maxn]; | |
| int n, m, dist[maxn]; | |
| void bfs(int x) { | |
| memset(dist, 0x3f3f3f3f, sizeof dist); // Inicializando distancia como "infinito" | |
| dist[x] = 0; | |
| deque<int> fila; | |
| fila.push_back(x); | |
| while (!fila.empty()) { | |
| int u = fila.front(); | |
| fila.pop_front(); | |
| for(int i = 0; i < (int)grafo[u].size(); i++) { | |
| int v = grafo[u][i].first; | |
| int d = grafo[u][i].second; | |
| if(dist[v] > dist[u] + d) { | |
| dist[v] = dist[u] + d; | |
| if(d == 1) fila.push_back(v); // Caso a distancia seja 1, insere o vertice normalmente na fila | |
| else fila.push_front(v); // Caso seja 0, insere como prioridade. | |
| } | |
| } | |
| } | |
| } | |
| int main(){ | |
| ios::sync_with_stdio(false), cin.tie(0); | |
| cin >> n >> m; | |
| for(int i=1;i<=m;i++){ | |
| int a, b, c; | |
| cin >> a >> b >> c; | |
| grafo[a].push_back({b, c}); | |
| grafo[b].push_back({a, c}); | |
| } | |
| bfs(1); | |
| cout << dist[n] << "\n"; | |
| return 0; | |
| } |

