전기가 부족해 (feat. 백준, 10423번)

전기가 부족해
https://www.acmicpc.net/problem/10423

10423번: 전기가 부족해

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> arr[1001];       // 다음 도시, 비용
bool visit[1001]{false};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;           // 비용, 다음 도시
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, K, ans = 0;
    cin >> N >> M >> K;
    for(register int k = 0, v; k < K; ++k)
        cin >> v, q.push(make_pair(0, v));
    for(register int m = 0, u, v, w; m < M; ++m)
        cin >> u >> v >> w, arr[u].push_back(make_pair(v, w)), arr[v].push_back(make_pair(u, w));
    while(!q.empty()){
        register int cost = q.top().first, next = q.top().second, nnext = 0; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        ans += cost;
        for(auto& p : arr[next])
            nnext = p.first, cost = p.second, q.push(make_pair(cost, nnext));
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

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

저는 프림 알고리즘을 통해 풀이하였습니다.