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[305];
  6. int parent[305],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.      int t=1;
  17.      m=(n-1)*n/2;
  18.      int k=m+n;
  19.     for(int i=m;i<=k;i++){
  20.         cin>>p;
  21.         e[i].first=p;
  22.         e[i].second.first=n+1;
  23.         e[i].second.second=t;
  24.         t++;
  25.     }
  26.  
  27.     for(int i=1;i<=m;i++){
  28.         cin>>u>>v>>w;
  29.         e[i].first=w;
  30.         e[i].second.first=u;
  31.         e[i].second.second=v;
  32.     }
  33.  
  34.     sort(e+1,e+1+k);
  35.     for(int i=1;i<=n+1;i++){
  36.         parent[i]=i;
  37.     }
  38.     for(int i=1;i<=k;i++){
  39.         int u=e[i].second.first;
  40.         int v=e[i].second.second;
  41.         int w=e[i].first;
  42.         int x=root(u);
  43.         int y=root(v);
  44.         if(x!=y){
  45.             parent[y]=x;
  46.             res+=w;
  47.             cnt++;
  48.  
  49.         }
  50.         if(cnt==n){
  51.             break;
  52.         }
  53.     }
  54.     cout<<res;
  55. }
  56.  
Success #stdin #stdout 0.01s 5312KB
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 
8
https://ideone.com/deY5GZ
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!