제출 #968867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968867		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	60 ms	4232 KiB

cities

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
const int MAX_N=2e5+5,INF=1e9+7;
int parent[MAX_N];
int find_root(int u){
    if(parent[u]==u) return u;
    return parent[u] = find_root(parent[u]);
}
bool try_merge(int u,int v){
    int root_u= find_root(u);
    int root_v = find_root(v);
    if(root_u!=root_v){
        parent[root_u]=root_v;
        return true;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,m,u,v,w;
    int tmp,tmp2;
    cin >> n >> tmp >> m;
    for(int i=0;i<tmp;++i) cin >> tmp2;
    vector<pair<int,pair<int,int>>> vec;
    for(int i=0;i<m;++i){
        cin >> u >> v >> w;
        vec.push_back({w, {u, v}});
    }
    for(int i=0;i<=n;++i) parent[i]=i;
    sort(vec.begin(),vec.end());
    long long cnt=0,idx=0,sum=0;
    while(cnt<n-1 && idx<m){
        u = vec[idx].second.first,v=vec[idx].second.second;
        w = vec[idx].first;
        if(try_merge(u,v)){
            cnt++;
            sum += w;
        }
        idx++;
    }
    cout << sum;
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26