Submission #3010873

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

const int MAX_V=101010;

int par[MAX_V]; //　親
int rnk[MAX_V]; // rank, 木の深さ

// V要素で初期化
void init(){
  for(int i=0;i<MAX_V;i++){
    par[i]=i;
    rnk[i]=0;
  }
}

// 木の根を求める
int find(int x){
  if (par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

// ｘとｙの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// ｘとｙが同じ集合に属するかどうか
bool same(int x, int y){
  return find(x) == find(y);
}

vector<pair<int,int> > V;
vector<pair<int,pair<int,int> > > E;

int main(){
    init();
    int N,M,K; cin>>N>>M>>K;
    rep(i,N){
        int c; cin>>c;
        V.push_back({c,i});
    }
    sort(V.begin(),V.end());
    rep(i,N-1) if(V[i].first!=0){
        if(V[i].first==V[i+1].first) unite(V[i].second,V[i+1].second);
    }
    rep(i,M){
        int a,b,w; cin>>a>>b>>w; a--,b--;
        E.push_back({w,{a,b}});
    }
    sort(E.begin(),E.end());
    int cnt=0;
    ll sum=0;
    rep(i,M){
        int w=E[i].first, u=E[i].second.first, v=E[i].second.second;
        if(!same(u,v)){
            unite(u,v);
            sum+=w;
            cnt++;
        }
        if(cnt>=K-1) break;
    }
    if(cnt<K-1) cout<<-1<<endl;
    else cout<<sum<<endl;
    return 0;
}

Submission Info

Judge Result