백준21202 Conquest

문제 링크

http://icpc.me/21202

사용 알고리즘

그리디

시간복잡도

$O(M \log N)$

풀이

유튜브 광고에서 자주 보이는 문제입니다.

갈 수 있는 정점 중 가중치가 가장 작은 정점부터 방문하면 된다는 것은 쉽게 알 수 있습니다. 이 전략을 효율적으로 구현해야 하는데, 최소 신장 트리를 구하는 Prim’s Algorithm을 $O(E \log V)$ 에 구현하는 것처럼 우선순위 큐를 사용하면 됩니다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int N, M, A[202020], C[202020], R;
vector<int> G[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=0,s,e; i<M; i++) cin >> s >> e, G[s].push_back(e), G[e].push_back(s);
    for(int i=1; i<=N; i++) cin >> A[i];
    R = A[1]; C[1] = 1;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> Q;
    for(auto i : G[1]) Q.emplace(A[i], i), C[i] = 1;
    while(!Q.empty()){
        auto [w,v] = Q.top(); Q.pop();
        if(w >= R) continue;
        R += w;
        for(auto i : G[v]) if(!C[i]) Q.emplace(A[i], i), C[i] = 1;
    }
    cout << R;
}