물대기 (feat. 백준, 1368번)

물대기 
https://www.acmicpc.net/problem/1368

1368번: 물대기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
bool visit[301]{false};
vector<pair<int, int>> arr[301];        // 다음 논, 비용
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, ans = 0;
    cin >> N;
    for(register int n = 1, v; n <= N; ++n)
        cin >> v, arr[0].push_back(make_pair(n, v)), arr[n].push_back(make_pair(0, v));     // 0과 n번째 논과의 비용
    for(register int i = 1, j, v; i <= N; ++i)
        for(j = 1; j <= N; ++j){
            cin >> v;
            if(i != j)
                arr[i].push_back(make_pair(j, v)), arr[j].push_back(make_pair(i, v));
        }
    q.push(make_pair(0, 0));
    while(!q.empty()){
        auto next = q.top().second, cost = q.top().first, nnext = 0; 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;
	return 0;
}
// *&)*@*

 

반응형

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

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

i번째 논에 우물을 팔때 드는 비용은 0번째 논과 이어준다고 생각한다면 쉽게 구할 수 있습니다.