BOJ 6497 전력난

1 개요

BOJ 6497 전력난
2 C++

#include <bits/stdc++.h>
using namespace std;

int m, n, sumDist;
typedef pair<int, int> Road;
vector<Road> v[200001];
bool visited[200001];

struct compare {
    bool operator()(Road a, Road b) {
        return a.second > b.second;
    }
};

void solve() {
    int answer = sumDist;
    memset(visited, 0, sizeof(visited));
    priority_queue<Road, vector<Road>, compare> pq;
    visited[0] = true;
    for (int i=0; i<v[0].size(); i++) pq.push(v[0][i]);
    while (!pq.empty()) {
        Road x = pq.top();
        pq.pop();
        if (visited[x.first]) continue;
        visited[x.first] = true;
        answer -= x.second;
        for (const auto& nx: v[x.first]) {
            if(visited[nx.first]) continue;
            pq.push(nx);
        }
    }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        cin >> m >> n;
        if (m == 0 && n == 0) break;
        for (int i=0; i<m; i++) {
            v[i].clear();
        }
        sumDist = 0;
        int x, y, z;
        for(int i=0; i<n; i++) {
            cin >> x >> y >> z;
            v[x].push_back({y, z});
            v[y].push_back({x, z});
            sumDist += z;
        }
        solve();
    }
}