Informática Ideia 07 - BFS 0-1

Feito por Thiago Mota

Menor Caminho

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;
	}

view raw

ideia_07_01.cpp

hosted with ❤ by GitHub

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;
	}

view raw

ideia_07_02.cpp

hosted with ❤ by GitHub