Advertisement
Md_hosen_zisad

prims

Dec 10th, 2018
403
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<long long,int>
  4. vector<pii>v[100007];
  5. bool vis[100007];
  6. long long solve(int x)
  7. {
  8.     int y;
  9.     long long min_cost=0;
  10.     priority_queue<pii>p;
  11.     p.push({0,x});
  12.     while(!p.empty())
  13.     {
  14.         pii p1=p.top();
  15.         p.pop();
  16.         x=p1.second;
  17.         if(vis[x])continue;
  18.         min_cost-=p1.first;
  19.         vis[x]=true;
  20.  
  21.         for(int i=0;i<v[x].size();i++)
  22.         {
  23.             if(!vis[v[x][i].second])
  24.             {
  25.                 p.push({-1*v[x][i].first,v[x][i].second});
  26.             }
  27.         }
  28.     }
  29.     return min_cost;
  30. }
  31.  
  32. int main()
  33. {
  34.  
  35.     int x,y,nodes,edges;
  36.     long long cost;
  37.     cin>>nodes>>edges;
  38.     for(int i=0;i<edges;i++)
  39.     {
  40.         cin>>x>>y>>cost;
  41.         v[x].push_back({cost,y});
  42.         v[y].push_back({cost,x});
  43.     }
  44.     cout<<solve(1)<<endl;
  45.     return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement