Proble 19 : minimum spanning Using Prim's algorithm in c++

 

                    minimum spanning Using Prim's algorithm in c++

by Ujjal Roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

const int N=1000;

vector<pair<ll,ll>>adj[N];

int main()

{

   ll node,edge,i;

   cout<<"Enter number of node and edge : ";

   cin>>node>>edge;

   while(edge--)

   {

       cout<<"Enter U V and W : ";

       ll u,v,w;

       cin>>u>>v>>w;

       adj[u].push_back({v,w});

       adj[v].push_back({u,w});

   }

   ll vis[node];

   memset(vis,0,sizeof(vis));

   priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;

   //{weight,node}

   pq.push({0,0});

   ll sum;

   sum=0;

   while(!pq.empty())

   {

       ll pqnode,pqweight;

       pqnode=pq.top().second;

       pqweight=pq.top().first;

       pq.pop();

       if(vis[pqnode]==0)

       {

           vis[pqnode]=1;

           sum+=pqweight;

           for(i=0;i<adj[pqnode].size();i++)

           {

                ll child;

                child=adj[pqnode][i].first;

                if(vis[child]==0)

                {

                      ll wtd;

                wtd=adj[pqnode][i].second;

                pq.push({wtd,child});

                }

           }

       }

   }

   cout<<sum<<endl;

  return 0;

}