fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> uv;
  4. typedef pair<int ,uv> wuv;
  5. wuv e[1000000];
  6. int parent[1000000],res,u,v,w,cnt,n,m,p;
  7. int root(int k){
  8.     while(parent[k]!=k){
  9.         k=parent[k];
  10.     }
  11.     return k;
  12. }
  13.  
  14. int main(){
  15.     cin>>n;
  16.  
  17.      int t=m+1;
  18.      m=(n-1)*n/2;
  19.     int k=n*n/2;
  20.     for(int i=1;i<=n;i++){
  21.         cin>>p;
  22.         e[t].first=p;
  23.         e[t].second.first=i;
  24.         e[t].second.second=n+1;
  25.         t++;
  26.     }
  27.  
  28.     for(int i=1;i<=m;i++){
  29.         cin>>u>>v>>w;
  30.         e[i].first=w;
  31.         e[i].second.first=u;
  32.         e[i].second.second=v;
  33.     }
  34.  
  35.     sort(e+1,e+1+k);
  36.     for(int i=1;i<=n+1;i++){
  37.         parent[i]=i;
  38.     }
  39.     for(int i=1;i<=k;i++){
  40.         int u=e[i].second.first;
  41.         int v=e[i].second.second;
  42.         int w=e[i].first;
  43.         int x=root(u);
  44.         int y=root(v);
  45.         if(x!=y){
  46.             parent[y]=x;
  47.             res+=w;
  48.             cnt++;
  49.  
  50.         }
  51.         if(cnt==n){
  52.             break;
  53.         }
  54.     }
  55.     cout<<res;
  56. }
  57.  
Success #stdin #stdout 0s 5552KB
comments (?)
stdin
copy 
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
stdout
copy 
6
https://ideone.com/cnxjfO
language:
C++ (gcc 8.3)
created:
1 year 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!