네트워크 복구 백준 2211 (c++)

문제

https://www.acmicpc.net/problem/2211

해결 방안

• 첫째 문제에서 네트워크 선 마다 시간이 다 다르다고 이야기했다 (가중치가 다르다, 다익)

• 최소 간선수를 복구해야한다 -> n개의 노드가 있다면 n -1개의 간선을 복구하면된다.

• 여기서 최소 간선을 복구하되, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다는 커져서는 안된다는 말이 -> 다익스트라로 개선된 간선을 복구해야한다는 뜻이다.

• 여기서 출력을할 때 개선된 다익을 저장할려면 개선되는 부분에서 역추적하는 코드를 넣으면된다.

• 역추적 코드를 넣고 슈퍼컴퓨터를 루트로 하는 다익을 출력하면된다 .

소스

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<pair<int, int>> v[1001];
int dist[1001];
int parent[10001]; // 역 추적 배열 
void daik() {
    priority_queue<pair<int, int>, vector<pair<int, int>>> pq;

    pq.push({ 0, 1 });
    dist[1] = 0;
    while (!pq.empty())
    {
        int cost = -pq.top().first;
        int now =  pq.top().second;
        pq.pop();

        //이미 구한 거리가 더 짧으면 pass 
        if (dist[now] < cost) continue;

        for (int i = 0; i < v[now].size(); i++)
        {
            int nx = v[now][i].first;
            int nxCost =  cost  + v[now][i].second; // 현재까지의 거리 + 간선의 가중치 

            if (nxCost < dist[nx]) {
                dist[nx] = nxCost;
                pq.push({ -nxCost, nx });
                parent[nx] = now;
            }
        }
    }
}
int main() {

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a = 0, b = 0, c = 0; 
        cin >> a >> b >> c;
        v[a].push_back({ b, c });
        v[b].push_back({ a, c });
    }

    for (int i = 1; i <= n; i++)
    {
        dist[i] = INT_MAX;
    }

    daik();

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (parent[i]) ans++;
    }

    cout << ans << endl;

    for (int i = 1; i <= n; i++)
    {
        if(parent[i]) cout << i << " " << parent[i] << endl;
    }
    return 0;
}