Module: bfs. khóa học nâng cao


Problem

1/3

0-1 BFS: Bắt đầu (C++)

Theory Click to read/hide

0-1 BFS
Để giải quyết vấn đề này, chúng tôi sửa đổi thuật toán BFS tiêu chuẩn bằng cách sử dụng deques ( deque ): nếu cạnh được xem xét có trọng số bằng 0, thì chúng tôi sẽ thêm một đỉnh vào đầu, nếu không kết thúc. 
Như vậy, ở đầu deque sẽ luôn tồn tại một đỉnh mà khoảng cách đến đỉnh đó nhỏ hơn hoặc bằng khoảng cách đến các đỉnh còn lại của deque và yêu cầu sắp xếp các phần tử trong deque theo thứ tự không giảm là được bảo toàn.
Để triển khai thuật toán 0-1 BFS, hãy xem chính vấn đề đó.

Problem

Cho hình ảnh của một đồ thị vô hướng (có các cạnh trọng số 0 và 1), hãy in danh sách các khoảng cách ngắn nhất từ ​​đỉnh 0 đến tất cả các đỉnh khác.
 
Đầu vào 
Cho hình ảnh của một đồ thị vô hướng với các cạnh 0 và 1.
 
Đầu ra
Trong câu trả lời của bạn, hãy đưa ra danh sách các đường đi ngắn nhất từ ​​đỉnh 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!