We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<cmath>#include<cstdio>#include<vector>#include<iostream>#include<algorithm>#include<queue>#include<unordered_set>usingnamespacestd;classGraph{public:vector<int>*adj;intV;Graph(intV){this->V=V;adj=newvector<int>[V];}voidadd_edge(intu,intv){adj[u].push_back(v);adj[v].push_back(u);}vector<int>shortest_reach(intstart,intn){vector<int>distances(n,-1);queue<int>que;unordered_set<int>seen;que.push(start);distances[start]=0;seen.insert(start);while(!que.empty()){intcur=que.front();que.pop();for(intnode:adj[cur]){if(seen.find(node)==seen.end()){que.push(node);seen.insert(node);distances[node]=distances[cur]+6;}}}returndistances;}};intmain(){intqueries;cin>>queries;for(intt=0;t<queries;t++){intn,m;cin>>n;// Create a graph of size n where each edge weight is 6:Graphgraph(n);cin>>m;// read and set edgesfor(inti=0;i<m;i++){intu,v;cin>>u>>v;u--,v--;// add each edge to the graphgraph.add_edge(u,v);}intstartId;cin>>startId;startId--;// Find shortest reach from node svector<int>distances=graph.shortest_reach(startId,n);for(inti=0;i<distances.size();i++){if(i!=startId){cout<<distances[i]<<" ";}}cout<<endl;}return0;}
Fixed the code from previous post, it is worth to point out a trivial mistake seen.find(node) != seen.end() should rather be seen.find(node) == seen.end() as revised.
BFS: Shortest Reach in a Graph
You are viewing a single comment's thread. Return to all comments →
Fixed the code from previous post, it is worth to point out a trivial mistake seen.find(node) != seen.end() should rather be seen.find(node) == seen.end() as revised.