도시 건설 (feat. 백준, 21924번)

도시 건설
https://www.acmicpc.net/problem/21924

21924번: 도시 건설

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visit[100001]{false};
vector<pair<int, long long>> arr[100001];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, a, b;
    register long long c, total = 0;
    cin >> N >> M;
    for(register int m = 0; m < M; ++m)
        cin >> a >> b >> c, total += c, arr[a].push_back(make_pair(b, c)), arr[b].push_back(make_pair(a, c));
    q.push(make_pair(0, 1));
    while(!q.empty()){
        auto next = q.top().second, nnext = 0;
        auto cost = q.top().first; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        total -= cost;
        for(auto& v : arr[next]){
            nnext = v.first, cost = v.second;
            if(!visit[nnext])
                q.push(make_pair(cost, nnext));
        }
    }
    if(find(&visit[1], &visit[N + 1], false) == &visit[N + 1])
        cout << total;
    else
        cout << -1;
    return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 프림 알고리즘을 활용하였습니다.

전체 도로를 만드는 비용에서 MST의 간선간 비용을 빼면 해답이 됩니다.

물론 MST가 만족되는 경우에만 해답을 출력해야 하므로 이를 주의해야 합니다.