제출 #1347563

#제출 시각아이디문제언어결과실행 시간메모리
1347563Zone_zoneeCities (BOI16_cities)C++20
0 / 100
43 ms5356 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10, K = 6;

int city[K];
struct x{
    int p;
    int mask;
    void bit_or(int b){
        mask |= b;
    }
} par[N];
x fp(int u){
    return par[u] = (u == par[u].p ? par[u] : fp(par[u].p));
}
vector<tuple<int, int, ll>> E;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; ++i) par[i] = {i, 0};
    for(int i = 1; i <= k; ++i) cin >> city[i], par[city[i]].bit_or(1<<(i-1));
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        E.push_back({w, u, v});
    }
    sort(E.begin(), E.end());
    ll ans = 0;
    for(auto [w, u, v] : E){
        x pu = fp(u), pv = fp(v);
        if(pu.p == pv.p) continue;
        ans += w;
        par[pv.p].bit_or(par[pu.p].mask);
        par[pu.p] = par[pv.p];
        if(par[pv.p].mask == (1<<k) - 1) break;
    }
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...