Networking (feat. 백준, 3803번)

Networking
https://www.acmicpc.net/problem/3803

3803번: Networking

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    while(1){
        cin >> N;
        if(N == 0)
            break;
        cin >> M;
        register int ans = 0;
        bool visit[51]{false};
        vector<pair<int, int>> arr[51];
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        for(register int m = 0, a, b, c; m < M; ++m){
            cin >> a >> b >> 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 nnext = 0, next = q.top().second, cost = q.top().first; q.pop();
            if(visit[next])
                continue;
            visit[next] = true;
            ans += cost;
            for(auto& v : arr[next]){
                nnext = v.first, cost = v.second;
                if(!visit[nnext])
                    q.push(make_pair(cost, nnext));
            }
        }
        cout << ans << '\n';
    }
	return 0;
}
// *&)*@*

 

반응형

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

MST를 구하기 위해 크루스칼 알고리즘과 프림 알고리즘 중 프림 알고리즘을 사용하였습니다.