fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define m_p make_pair
  5. #define pb push_back
  6. typedef pair<ll,ll> pii;
  7. vector <pair<ll,pii> >adj;
  8. ll par[100009];
  9. ll siz[100009];
  10.  
  11. ll root(ll i)
  12. {
  13.     while(i!=par[i])
  14.     {
  15.         par[i]=par[par[i]];
  16.         i=par[i];
  17.     }
  18.     return i;
  19. }
  20. void joins(ll i,ll j)
  21. {
  22.     ll root_i=root(i);
  23.     ll root_j=root(j);
  24.     if(siz[root_i]<siz[root_j])
  25.     {
  26.         par[root_i]=par[root_j];
  27.         siz[root_j]+=siz[root_i];
  28.     }
  29.     else
  30.     {
  31.         par[root_j]=par[root_i];
  32.         siz[root_i]+=siz[root_j];
  33.     }
  34.  
  35.  
  36. }
  37. bool finds(ll i,ll j)
  38. {
  39.     if(root(i)==root(j))
  40.         return true;
  41.     else
  42.         return false;
  43.  
  44. }
  45. int main()
  46. {
  47.     ll t;
  48.     cin>>t;
  49.     while(t--)
  50.     {
  51.  
  52.         ll a,b,c,v;
  53.         scanf("%lld",&v);
  54.         for(ll i=1;i<=v;i++)
  55.         {
  56.             siz[i]=1;
  57.             par[i]=i;
  58.         }
  59.         for(ll i=1;i<=v;i++)
  60.         {
  61.             string str;
  62.             scanf("%s",str);
  63.             ll n;
  64.             scanf("%lld",&n);
  65.             for(ll j=0;j<n;j++)
  66.             {
  67.                 scanf("%lld%lld",&a,&b);
  68.                 adj.pb({b,{i,a}});
  69.                 adj.pb({b,{a,i}});
  70.             }
  71.         }
  72.         sort(adj.begin(),adj.end());
  73.  
  74.         // vector <pair<ll,pii> >adj;
  75.         ll wt=0;
  76.  
  77.         for(auto ii : adj)
  78.         {
  79.             ll temp_wt=ii.first;
  80.             ll vertex1=ii.second.first;
  81.             ll vertex2=ii.second.second;
  82.             if(!finds(vertex1,vertex2))
  83.             {
  84.                 wt+=temp_wt;
  85.                 joins(vertex1,vertex2);
  86.             }
  87.         }
  88.         cout<<wt<<endl;
  89.         adj.clear();
  90.     }
  91.  
  92.  
  93. }
  94.  
Runtime error #stdin #stdout 0s 4876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/drmNMY
language:
C++ (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!