Problem

1/3

0-1 BFS : Début (C++)

Theory Click to read/hide

0-1 BFS
Pour résoudre ce problème, nous modifions l'algorithme BFS standard en utilisant deques ( deque ) : si l'arête considérée a un poids de 0, alors nous ajouterons un sommet au début, sinon à la fin.
Ainsi, au début du deque, il y aura toujours un sommet dont la distance est inférieure ou égale à la distance aux autres sommets du deque, et l'obligation d'organiser les éléments du deque dans un ordre non décroissant est conservé.
Pour l'implémentation de l'algorithme 0-1 BFS, voir le problème lui-même.

Problem

Étant donné une image d'un graphe non orienté (avec des arêtes de poids 0 et 1), imprimez une liste des distances les plus courtes du sommet 0 à tous les autres.
 
Entrée 
Une image d'un graphe non orienté avec des arêtes 0 et 1 est donnée.
 
Sortie
Dans votre réponse, affichez une liste des chemins les plus courts à partir du sommet 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!