방탈출 (feat. 백준, 23743번)

방탈출
https://www.acmicpc.net/problem/23743

23743번: 방탈출

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> arr[200001];
bool visit[200001]{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, ans = 0;
    cin >> N >> M;
    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));
    for(register int n = 1, t; n <= N; ++n)
        cin >> t, arr[0].push_back(make_pair(n, t)), arr[n].push_back(make_pair(0, t));
    q.push(make_pair(0, 0));
    while(!q.empty()){
        auto time = q.top().first, next = q.top().second, nnext = 0; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        ans += time;
        for(auto& v : arr[next]){
            nnext = v.first, time = v.second;
            if(!visit[nnext])
                q.push(make_pair(time, nnext));
        }
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

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

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

마지막 한줄이 의미하는 비상탈출구 시간이 트릭이지만 문제에서 주어지는 1번-N번방 외에 0번방을 생성하여 모두 이어진다면 이를 통해 MST를 쉽게 구할 수 있습니다.