Maruf_Hasan

Prims algo new

Sep 18th, 2019
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include<bits//stdc++.h>
  2. using namespace std;
  3. int visited[1000]={0};
  4. vector<int>edge[1000];
  5. vector<int>cost[1000];
  6. struct data
  7. { int v,w;
  8. bool operator < ( data p ) const {
  9. return w > p.w;
  10. }
  11. };
  12. int Prims(int src,int n)
  13. {
  14. priority_queue<data>pq;
  15. int i,u,v,sum=0,j,p;
  16. for(i=0;i<n-1;i++)
  17. {
  18. u=src;
  19. visited[src]=1;
  20.  
  21. for(j=0;j<edge[u].size();j++)
  22. {
  23. v=edge[u][j];
  24. if(visited[v]==0)
  25. {
  26. data D; D.v=v;
  27. D.w=cost[u][j];
  28. pq.push(D);
  29. }
  30. }
  31. while(visited[src]){
  32. data T=pq.top();pq.pop();
  33. src=T.v;p=T.w;
  34. }
  35. sum+=p;
  36. }
  37. return sum;
  38. }
  39. int main()
  40. {
  41. freopen("in.txt","r",stdinn1,n2,w,i;
  42. scanf("%d %d",&n,&e);
  43. for(i=0;i<e;i++)
  44. {
  45. scanf("%d %d %d",&n1,&n2,&w);
  46. edge[n1].push_back(n2);
  47. edge[n2].push_back(n1);
  48. cost[n1].push_back(w);
  49. cost[n2].push_back(w);
  50. }
  51. printf("%d\n",Prims(1,n));
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment