Maruf_Hasan

Prim's Algorithm incomplete

Sep 17th, 2019
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.73 KB | None | 0 0
  1. #define pii pair<int,int>
  2. #define vpi vector<pii>
  3. #define ff first
  4. #define ss second
  5.  
  6. vpi V[3005]; //graph is stored here as adjacency list
  7. int vis[3005]={0};
  8.  
  9. int prim()
  10. {
  11. priority_queue<pii> p; //stored as <cost,node> pair
  12. int cost = 0;
  13. p.push(mp(0,0)); //source is 0, and cost of source to source is 0
  14. while(!p.empty())
  15. {
  16. pii tem = p.top();
  17. p.pop();
  18. int v = tem.ss;
  19. if(!vis[v])
  20. {
  21. vis[v] = 1;
  22. cost += -tem.ff;
  23. For(i,V[v].sz)
  24. if(!vis[V[v][i].ff])
  25. p.push(mp(-(V[v][i].ss),V[v][i].ff));
  26. }
  27. }
  28. return cost;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment