Module: mejor amigo curso avanzado


Problem

1/3

0-1 BFS: Principio (C++)

Theory Click to read/hide

0-1 BFS
Para resolver este problema, modificamos el algoritmo BFS estándar usando deques ( deque ): si la arista considerada tiene un peso de 0, entonces agregaremos un vértice al principio, de lo contrario a el final. 
Por lo tanto, al comienzo del deque siempre habrá un vértice, cuya distancia es menor o igual que la distancia a los otros vértices del deque, y el requisito de disponer los elementos en el deque en orden no decreciente es preservado.
Para la implementación del algoritmo 0-1 BFS, vea el problema en sí.

Problem

Dada una imagen de un gráfico no dirigido (tiene bordes de peso 0 y 1), imprima una lista de las distancias más cortas desde el vértice 0 a todos los demás.
 
Entrada 
Se da una imagen de un gráfico no dirigido con bordes 0 y 1.
 
Salida
En su respuesta, genere una lista de las rutas más cortas desde el 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!