Module: bfs. 고급 코스


Problem

1/3

0-1 BFS: 시작(C++)

Theory Click to read/hide

0-1 BFS
이 문제를 해결하기 위해 deques( deque )를 사용하여 표준 BFS 알고리즘을 수정합니다. 고려되는 가장자리의 가중치가 0이면 정점을 시작 부분에 추가하고 그렇지 않으면 끝. 
따라서 deque의 시작 부분에는 항상 정점이 있으며, 그 거리는 deque의 다른 정점까지의 거리보다 작거나 같으며, deque의 요소를 감소하지 않는 순서로 배열해야 하는 요구 사항은 다음과 같습니다. 보존.
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!