고속철도 설계하기 (feat. 백준, 1833번)

고속철도 설계하기
https://www.acmicpc.net/problem/1833

1833번: 고속철도 설계하기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Node{
    int cost;
    int from;
    int to;
};
struct cmp{
    bool operator()(Node& v1, Node& v2){
        if(v1.cost == v2.cost){
            if(v1.from == v2.from){
                return v1.to > v2.to;
            }
            return v1.from > v2.from;
        }
        return v1.cost > v2.cost;
    }
};
bool visit[201]{false};
vector<pair<int, int>> arr[201];
priority_queue<Node, vector<Node>, cmp> q;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    register long long ans = 0;
    cin >> N;
    for(register int i = 1, j, v; i <= N; ++i)
        for(j = 1; j <= N; ++j){
            cin >> v;
            if(i != j){
                if(v < 0)
                    ans += abs(v), arr[i].push_back(make_pair(j, 0));
                else
                    arr[i].push_back(make_pair(j, v));
            }
        }
    ans /= 2;
    vector<pair<int, int>> tmp;
    q.push(Node{0, 0, 1});
    while(!q.empty()){
        auto from = q.top().from, to = q.top().to, cost = q.top().cost; q.pop();
        if(visit[to])
            continue;
        visit[to] = true;
        ans += cost;
        if(cost > 0)
            tmp.push_back(make_pair(min(from, to), max(from, to)));
        from = to;
        for(auto& v : arr[from]){
            to = v.first, cost = v.second;
            if(!visit[to])
                q.push(Node{cost, from, to});
        }
    }
    cout << ans << ' ' << tmp.size() << '\n';
    for(auto& t : tmp)
        cout << t.first << ' ' << t.second << '\n';
    return 0;
}
// *&)*@*

 

반응형

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

저는 프림 알고리즘을 활용했습니다.

해당 문제에서 1000 이라는 값은 예제에서 사용하지 않았다는 것일뿐, 실제 데이터에는 반영되어야 하는 값입니다.

즉, 최소 스패닝 트리를 구하기 위한 간선에 추가되어야 하는 값이라는 의미입니다.