Submission #60541911

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
template <class T>using pqg = priority_queue<T, vector<T>, greater<T>>;  // ascendent
int main(){
  int n, m, k;
  cin >> n >> m >> k;
  pqg<pair<int, pair<int, int>>> pq;
  for(int i = 0; i < m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    pq.emplace(w, make_pair(u-1, v-1));
  }
  vector<int> ab(n, 0); //aが1つある:+
  for(int i = 0; i < k; i++){
    int a;
    cin >> a;
    ab[a-1]++;
  }
  for(int i = 0; i < k; i++){
    int b;
    cin >> b;
    ab[b-1]--;
  }
  // for(int i = 0; i < n; i++) cout << ab[i] << " \n"[i==n-1];
  long long ans = 0;
  atcoder::dsu uf(n);
  while(!pq.empty()){
    int w;
    pair<int, int> p;
    tie(w, p) = pq.top();
    pq.pop();
    if(uf.same(p.first, p.second)) continue;
    int x = ab[uf.leader(p.first)];
    int y = ab[uf.leader(p.second)];
    if((x>0&&y<0)||(x<0&&y>0)) ans += (long long)w*min(abs(x), abs(y));
    uf.merge(p.first, p.second);
    ab[uf.leader(p.first)] = x+y;
  }
  cout << ans << endl;
}

Submission Info

Judge Result