Module: namorados curso avançado


Problem

1/3

0-1 BFS: Início (C++)

Theory Click to read/hide

0-1 BFS
Para resolver este problema, modificamos o algoritmo BFS padrão usando deques ( deque ): se a aresta considerada tiver peso 0, adicionaremos um vértice ao início, caso contrário fim. 
Assim, no início do deque sempre haverá um vértice, cuja distância é menor ou igual à distância dos demais vértices do deque, e a exigência de dispor os elementos no deque em ordem não decrescente é preservado.
Para a implementação do algoritmo 0-1 BFS, veja o problema em si.

Problem

Dada a imagem de um grafo não direcionado (com arestas de peso 0 e 1), imprima uma lista das distâncias mais curtas do vértice 0 a todos os outros.
 
Entrada 
Uma imagem de um grafo não direcionado com arestas 0 e 1 é dada.
 
Saída
Em sua resposta, gere uma lista de caminhos mais curtos a partir do vértice 0.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <vector>
#include <deque>
#include <vector>
#include <limits>

#define V 9 

using namespace std;

struct node
{
	int to, weight;
};

vector <node> edges[V];
void bfs_0_1(int start) {
	int INF = numeric_limits<int>::max();
	deque <int > Q;
	vector <int > dist(V, INF);
	dist[start] = 0;
	Q.push_back(start);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop_front();
		for (auto edge : edges[u]) {
			if (dist[edge.to] > dist[u] + edge.weight) {
				dist[edge.to] = dist[u] + edge.weight;
				if(edge.weight == 0 )
                                         Q.push_front(edge.to); 
                                 else
                                         Q.push_back(edge.to);
			}

		}
	}
	for (int i = 0; i < V; i++)
		cout << dist[i] << " ";
}

void addEdge(int u, int v, int wt)
{
	edges[u].push_back({ v, wt });
	edges[v].push_back({ u, wt });
}


int main()
{
	addEdge(0, 1, 0);
	// остальные ребра добавьте сами сами           
	bfs_0_1(0);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!