[백준][C++] 14950 정복자

www.acmicpc.net/problem/14950

14950번: 정복자

 

 

 

알고리즘 종류

    - MST

    - Prim

 

 

 

사고 과정

    - 모든 노드를 최소 비용으로 연결하는 MST 문제이다. 그런데 간선 기준이 아닌 노드 기준으로 탐색되고 있다. 따라서 Prim 알고리즘을 사용한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m, t;
int answer=0;
 
int isVisited[10001];
vector<vector<pair<int, int> > > edges;
priority_queue<pair<int, int> > pq;
 
 
void prim(int here, int cnt){
    
    isVisited[here] = 1;
    
    // 시작 노드에서 연결된 간선들 중에 가장 비용이 적은 간선 뽑을 준비  
    for(int i=0; i<edges[here].size(); i++){
        int next = edges[here][i].first;
        int cost = edges[here][i].second;
        
        if(isVisited[next]==0) pq.push({-cost, next});
    }
    
    // 비용이 가장 적은 간선 뽑아서 연결하기  
    while(!pq.empty()){
        int next = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        
        if(isVisited[next]) continue;
        answer+= cost + cnt*t;
        prim(next, cnt+1);
        return;
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> t;
    edges.resize(n+1);
    
    int a,b,c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    
    prim(1, 0);
    cout << answer << endl;
}

 

 

 

시행착오