One if condition is missing from Prims Efficient solution #16

Activity

1. amantayal6797 commented on Jul 8, 2021

   

   amantayal6797

   on Jul 8, 2021

   Author

   More actions

   This is the correct code for the gfg problem

   int spanningTree(int V, vector<vector> adj[]){
   int res=0;
   vector MST(V,false);
   vector dist(V,INT_MAX);
   dist[0]=0;
   priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
   q.push({0,0});

   while(q.size()!=0){
   int ver;
   ver=q.top().second;
   q.pop();
   if(MST[ver]==true) //This is very important
   continue;

   MST[ver]=true;
   res+=dist[ver];

   for(int j=0;j<adj[ver].size();j++){
   int v=adj[ver][j][0];
   int wt=adj[ver][j][1];
   if(MST[v]==false && dist[v]>wt){
   dist[v] = wt;
   q.push({dist[v],v});
   }
   }
   }
   return res;
   }