[BOJ/C++/1647] 도시 분할 계획

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,c,cnt,res,MAX;
vector<pair<int,int>> v[100001]; // node, value
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>,greater<tuple<int,int,int>> > pq; // value, node1, node2
bool check[100001];
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    check[1]=true;
    for(auto nxt:v[1])
        pq.push(make_tuple(nxt.second,1,nxt.first));
    while(cnt<n-1){
        int cost,x,y; tie(cost,x,y)=pq.top(); pq.pop();
        if(check[y]) continue;
        cnt++;
        res+=cost;
        MAX=max(MAX,cost);
        check[y]=true;
        for(auto nxt:v[y])
            if(!check[nxt.first])
                pq.push(make_tuple(nxt.second,b,nxt.first));
    }
    cout<<res-MAX;
    return 0;
}