[Dijkstra] BOJ 2211 네트워크 복구

문제 링크 : www.acmicpc.net/problem/2211

2211번: 네트워크 복구

문제를 자세히 읽지 않는다면 최소 스패닝 트리(MST) 문제로 혼동할 수 있다.

제시된 조건 중,

"따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다."

라는 내용이 있기 때문에 이 문제는 최소 스패닝 트리로 해결할 수 없게 된다. 다음과 같은 반례를 들 수 있다.

그림에서 붉은 색으로 칠한 간선들이 위 그래프의 MST를 이룬다.

하지만, 1번 노드로부터 3번 노드까지의 최단거리는 6으로, MST를 구성했을 때 전송 거리인 7보다 더 작은 값이다.

이는 위에서 언급한 조건을 만족하지 않으므로, MST 알고리즘으로는 항상 최적의 해를 구할 수 없다.

 

즉, 출발 노드인 1번 노드로부터 다른 모든 노드까지의 최단경로에 포함된 간선들의 집합을 구하는 문제임을 알 수 있다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> pp;
 
int n, m, dist[1001], prevnode[1001];
vector<p> answer;
vector<p> adj[1001];
bool visit[1001][1001];
 
void dijkstra() {
    priority_queue<p> pque;
    pque.push({ 0, 1 });
    dist[1] = 0;
 
    while (!pque.empty()) {
        p cur = pque.top();
        pque.pop();
 
        int node = cur.second;
        int distval = -cur.first;
 
        if (distval <= dist[node]) {
            for (int i = 0; i < adj[node].size(); i++) {
                int nextnode = adj[node][i].first;
                int newdist = distval + adj[node][i].second;
 
                if (newdist < dist[nextnode]) {
                    dist[nextnode] = newdist;
                    pque.push({ -newdist, nextnode });
                    prevnode[nextnode] = node;
                }
            }
        }
    }
}
 
void get_answer(int node) {
    //1 ~ node까지의 최단경로에 사용된 간선들을 구해 저장
    while (node != 1) {
        if (!visit[node][prevnode[node]]) {
            visit[node][prevnode[node]] = true;
            answer.push_back({ node, prevnode[node] });
        }
        node = prevnode[node];
    }
}
 
void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        prevnode[i] = i;
        dist[i] = INF;
    }
 
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dijkstra();
    for (int i = 2; i <= n; i++) get_answer(i);
 
    printf("%d\n", answer.size());
    for (int i = 0; i < answer.size(); i++) printf("%d %d\n", answer[i].first, answer[i].second);
 
    //system("PAUSE");
    return 0;
}