Module: 男朋友。高级课程


Problem

1/3

0-1 BFS：开始（C++）

Theory Click to read/hide

0-1 BFS
为了解决这个问题，我们使用双端队列 ( deque ) 修改标准 BFS 算法： 如果所考虑的边的权重为 0，那么我们将在开头添加一个顶点，否则为结束。 
因此，在双端队列的开头总会有一个顶点，到该顶点的距离小于或等于到双端队列其他顶点的距离，并且要求双端队列中的元素按非降序排列保留。
0-1 BFS算法的实现，参见问题本身。

Problem

给定一个无向图的图像（边的权重为 0 和 1），打印从顶点 0 到所有其他顶点的最短距离列表。
 
输入 
给出了边为 0 和 1 的无向图的图像。
 
输出
在您的答案中，输出从顶点 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!