Module: BFS. Weiterführender Kurs


Problem

1/3

0-1 BFS: Anfang (C++)

Theory Click to read/hide

0-1 BFS
Um dies zu erreichen, wird der Standard-BFS-Algorithmus mittels dec (deque : Wenn die betreffende Rippe ein Gewicht von 0 hat, werden wir die Spitze zu Beginn oder sonst zum Ende hinzufügen.
So wird es zu Beginn der Deka immer einen Peak geben, der kleiner oder gleich dem Rest der Platte ist, und die Anforderung von Deck bleibt.
Realisierung des Algorithmus 0-1 BFS Sieh dir die Herausforderung an.

Problem

Für das angegebene Bild des nicht ausgerichteten Graphen (hat Kanten mit einem Gewicht von 0 und 1), geben Sie eine Liste der kürzesten Abstände vom Scheitelpunkt 0 zu allen anderen aus.
 
Eingabe 
Es wurde ein Bild eines nicht ausgerichteten Graphen mit den Kanten 0 und 1 gegeben.
 
Ausgabe
Geben Sie in der Antwort die Liste der kürzesten Pfade vom Scheitelpunkt 0 aus.

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!