Module: bfs。上級コース


Problem

1/3

0-1 BFS: 始まり (C++)

Theory Click to read/hide

0-1 BFS
この問題を解決するには、deques ( 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!