정복자 (feat. 백준, 14950번)

정복자
https://www.acmicpc.net/problem/14950

14950번: 정복자

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<short, short>> arr[10001];      // 다음 도로, 두 도로간 비용
bool visit[10001]{false};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;      // 두 도로간 비용, 다음 도로
int ans = 0;
void func(register short next, register int cnt, register short& t){
    register short nnext, cost;
    visit[next] = true;
    for(auto& v : arr[next]){
        nnext = v.first, cost = v.second;
        if(!visit[nnext])
            q.push(make_pair(cost, nnext));
    }
    while(!q.empty()){
        cost = q.top().first, next = q.top().second; q.pop();
        if(visit[next])
            continue;
        ans += cost + cnt * t;
        return func(next, cnt + 1, t);
    }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register short N, M, t;
    cin >> N >> M >> t;
    for(register short 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));
    func(1, 0, t);
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

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

정복을 할때마다 t만큼 증가되는 조건에서 많이 헤맸습니다.

저는 프림 알고리즘을 통해 풀이하였고 정복할때마다 의 조건 때문에 재귀 호출을 통해 누적값을 구했습니다.