fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define str string
  6. #define pu push
  7. #define pb push_back
  8. #define pii pair<long long,long long>
  9. #define piii pair<pii,long long>
  10. #define __MaCodVN__ signed main()
  11. #define task "CHECKIN"
  12.  
  13. const ll N=5e5+9;
  14. const ll mxN= 1e6+9;
  15. const ll mod=1e9+7;
  16. const int AC=0;
  17.  
  18. using namespace std;
  19. ll n,tt,a[N],h[N],r[N],m,k,par[N],d[N];
  20. vector<piii> g;
  21. vector<ll> b[N];
  22.  
  23. ll get (ll u)
  24. {
  25.  if(u==r[u])
  26.    return r[u];
  27.  return r[u]=get(r[u]);
  28. }
  29.  
  30. void join (ll u,ll v)
  31. {
  32.  u=get(u);
  33.  v=get(v);
  34.  r[v]=u;
  35. }
  36.  
  37. void dsu (ll u,ll v)
  38. {
  39.  u=r[u];
  40.  v=r[v];
  41.  if(b[u].size()>b[v].size())
  42.   swap(u,v);
  43.  for(auto j:b[u])
  44.   {
  45.    r[j]=v;
  46.    b[v].pb(j);
  47.   }
  48.   d[v]+=d[u];
  49. }
  50.  
  51. bool check (ll u,ll  v)
  52. {
  53.  u=get(u);
  54.  v=get(v);
  55.  return (u==v);
  56. }
  57.  
  58. bool cmp (piii a,piii b)
  59. {
  60.  return a.se<b.se;
  61. }
  62.  
  63. void sub2()
  64. {
  65.  ll ans=0;
  66.  for(auto [x,w]:g)
  67.   {
  68.    ll u=x.fi,v=x.se;
  69.    if(!check(u,v))
  70.     {
  71.      ans+=w;
  72.      join(u,v);
  73.     }
  74.   }
  75.   cout<<ans;
  76. }
  77.  
  78. void sub3()
  79. {
  80.  ll ans=0;
  81.  for(ll i=1;i<=n;i++){
  82.    b[i].pb(i);
  83. //   ans+=i;
  84.  }
  85.  for(auto [x,w]:g)
  86.   {
  87.    ll u=x.fi,v=x.se;
  88.    if(r[u]!=r[v] && (d[r[v]]==0 || d[r[u]]==0))
  89.     {
  90.      //cout<<u<<" "<<v<<'\n';
  91.      ans+=w;
  92.      dsu(u,v);
  93.     }
  94.   }
  95.  for(ll i=1;i<=n;i++)
  96.   if(d[r[i]]==0)
  97.    {
  98.     cout<<"-1";
  99.     return;
  100.    }
  101.  cout<<ans;
  102. }
  103.  
  104.  
  105. void solve ()
  106. {
  107.  cin>>n>>m>>k;
  108.  for(ll i=1;i<=k;i++){
  109.    cin>>a[i];
  110.    d[a[i]]=1;
  111.  }
  112.  for(ll i=1;i<=n;i++)
  113.    r[i]=i;
  114.  for(ll i=1;i<=m;i++)
  115.   {
  116.    ll u,v,w;
  117.    cin>>u>>v>>w;
  118.    g.pb({{u,v},w});
  119.   }
  120.  sort(g.begin(),g.end(),cmp);
  121.  sub3();
  122. }
  123.  
  124. __MaCodVN__
  125. {
  126.  ios_base::sync_with_stdio(false);
  127.  cin.tie(NULL);cout.tie(NULL);
  128.  if(fopen(task".INP", "r")) {
  129.   freopen(task".INP", "r", stdin);
  130.   freopen(task".OUT", "w", stdout);
  131.  }
  132.  tt=1;
  133.  while(tt--)
  134.   solve();
  135.  return AC;
  136. }
  137.  
Success #stdin #stdout 0.01s 16348KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KMtAjm
language:
C++14 (gcc 8.3)
created:
8 days 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!