No Rules Rules

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

생활/코테

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

개발하는 완두콩 2023. 4. 19. 12:33
728x90
반응형

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

 

21924번: 도시 건설

첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두

www.acmicpc.net

 

// 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가 만족되는 경우에만 해답을 출력해야 하므로 이를 주의해야 합니다.

728x90
반응형
Comments