유럽여행 (feat. 백준, 1185번)

유럽여행
https://www.acmicpc.net/problem/1185

1185번: 유럽여행

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
short N, COST[10001];
int P;
vector<pair<short, int>> arr[10001];      // 다음 나라, 왕복 비용
bool visit[10001]{false};
priority_queue<pair<int, short>, vector<pair<int, short>>, greater<pair<int, short>>> q;      // 왕복 비용, 다음 나라
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> P;
    for(short n = 1; n <= N; ++n)
        cin >> COST[n];
    for(int p = 0; p < P; ++p){
        short S, E, L;
        cin >> S >> E >> L;
        arr[S].push_back(make_pair(E, COST[S] + COST[E] + 2 * L)), arr[E].push_back(make_pair(S, COST[E] + COST[S] + 2 * L));
    }
    short next, nnext;
    int cost, ans = *min_element(COST + 1, COST + N + 1);
    short min_value_pos = static_cast<short>(min_element(COST + 1, COST + N + 1) - COST);
    q.push(make_pair(0, min_value_pos));
    while(!q.empty()){
        cost = q.top().first, next = q.top().second; 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;
}
// *&)*@*

 

반응형

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

단순히 최단거리만을 구해선 안되고, 나라와 나라간 모든 비용을 미리 산술한 뒤에 가장 저렴한 나라에서 출발한다는 정의를 두고 풀이하였습니다.

저는 프림 알고리즘을 사용하여 풀이하였습니다.