Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define pii pair<int,int>
- #define vpi vector<pii>
- #define ff first
- #define ss second
- vpi V[3005]; //graph is stored here as adjacency list
- int vis[3005]={0};
- int prim()
- {
- priority_queue<pii> p; //stored as <cost,node> pair
- int cost = 0;
- p.push(mp(0,0)); //source is 0, and cost of source to source is 0
- while(!p.empty())
- {
- pii tem = p.top();
- p.pop();
- int v = tem.ss;
- if(!vis[v])
- {
- vis[v] = 1;
- cost += -tem.ff;
- For(i,V[v].sz)
- if(!vis[V[v][i].ff])
- p.push(mp(-(V[v][i].ss),V[v][i].ff));
- }
- }
- return cost;
- }
Advertisement
Add Comment
Please, Sign In to add comment