Module: bfs. ileri düzey kurs


Problem

1/3

0-1 BFS: Başlangıç ​​(C++)

Theory Click to read/hide

0-1 BFS
Bu sorunu çözmek için standart BFS algoritmasını deques ( deque ) kullanarak değiştiriyoruz: eğer dikkate alınan kenarın ağırlığı 0 ise, o zaman başlangıca bir tepe noktası ekleyeceğiz, aksi takdirde son. 
Bu nedenle, deque'nin başlangıcında her zaman bir tepe noktası olacaktır, mesafesi deque'nin diğer köşelerine olan mesafeden daha az veya ona eşittir ve deque'deki elemanları azalan olmayan bir düzende düzenleme gereksinimi korunmuş.
0-1 BFS algoritmasının uygulanması için sorunun kendisine bakın.

Problem

Yönlendirilmemiş bir grafiğin görüntüsü verildiğinde (kenarları 0 ve 1 ağırlıklı), 0 köşe noktasından tüm diğerlerine olan en kısa mesafelerin bir listesini yazdırın.
 
Giriş 
Kenarları 0 ve 1 olan yönsüz bir grafiğin görüntüsü verilmiştir.
 
Çıktı
Yanıtınızda, 0. köşe noktasından itibaren en kısa yolların bir listesini çıkarın.

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!