fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. struct edge
  7. {
  8.     ll x,y,w;
  9.     bool operator<(const edge &p) const
  10.     {
  11.         return w<p.w;
  12.     }
  13. } e[100005];
  14.  
  15. vector<edge>v;
  16.  
  17. ll pr[10005];
  18.  
  19. ll find(ll src)
  20. {
  21.     if(pr[src]==src)
  22.         return src;
  23.     return pr[src]=find(pr[src]);
  24. }
  25.  
  26. ll mst(ll n)
  27. {
  28.     sort(v.begin(),v.end());
  29.     ll s=0,len=v.size(),cnt=0,i;
  30.  
  31.     for(i=1; i<=n; i++)
  32.         pr[i]=i;
  33.     for(i=0; i<len; i++)
  34.     {
  35.         ll u=find(v[i].x);
  36.         ll v1=find(v[i].y);
  37.         if(u!=v1)
  38.         {
  39.             pr[u]=v1;
  40.             cnt++;
  41.             s+=v[i].w;
  42.             if(cnt==n-1)
  43.                 break;
  44.         }
  45.     }
  46.     return s;
  47. }
  48.  
  49. int main()
  50. {
  51.     ll i,j,n,m,t,a,b,c;
  52.     scanf("%lld%lld",&n,&m);
  53.  
  54.     for(i=0; i<m; i++)
  55.     {
  56.         scanf("%lld%lld%lld",&a,&b,&c);
  57.         edge g;
  58.         g.x=a;
  59.         g.y=b;
  60.         g.w=c;
  61.         v.push_back(g);
  62.     }
  63.     printf("%lld\n",mst(n));
  64. }
  65.  
Runtime error #stdin #stdout 4.64s 2096112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zwP309
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!