Module: bfs. corso avanzato


Problem

1/3

0-1 BFS: Inizio (C++)

Theory Click to read/hide

0-1 BFS
Per risolvere questo problema, modifichiamo l'algoritmo BFS standard utilizzando deques ( deque ): se lo spigolo considerato ha peso 0, allora aggiungeremo un vertice all'inizio, altrimenti per alla fine. 
Pertanto, all'inizio della deque ci sarà sempre un vertice, la cui distanza è minore o uguale alla distanza dagli altri vertici della deque, e il requisito per disporre gli elementi nella deque in ordine non decrescente è conservato.
Per l'implementazione dell'algoritmo 0-1 BFS, vedere il problema stesso.

Problem

Data un'immagine di un grafo non orientato (ha bordi di peso 0 e 1), stampa un elenco delle distanze più brevi dal vertice 0 a tutti gli altri.
 
Input 
Viene fornita un'immagine di un grafico non orientato con spigoli 0 e 1.
 
Uscita
Nella tua risposta, genera un elenco di percorsi minimi dal vertice 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!