네트워크 복구 2211

문제

접근 방법

문제가 너무 길고 단번에 이해하기 어렵게 적어놨다.
최소 스패닝 트리 문제 같지만

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

이 부분 덕분에 다익스트라라는 것을 알 수 있게 됐다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
int N, M, A, B, C;
vector<vector<pii>> graph;
vector<pii> ret;
vector<int> dist;
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    dist = vector<int>(N + 1, 100000);
    graph = vector<vector<pii>>(N + 1, vector<pii>());
    while (M--)
    {
        cin >> A >> B >> C;
        graph[A].push_back({B, C});
        graph[B].push_back({A, C});
    }
    pq.push({0, 0, 1});
    while (!pq.empty())
    {
        tiii curNode = pq.top();
        pq.pop();
        int value = get<0>(curNode);
        int prev = get<1>(curNode);
        int cur = get<2>(curNode);
        if (dist[cur] != 100000)
            continue;
        dist[cur] = value;
        ret.push_back({prev, cur});
        for (pii nextNode : graph[cur])
        {
            int next = nextNode.first;
            int nextValue = nextNode.second;
            if (value + nextValue >= dist[next])
                continue;
            pq.push({value + nextValue, cur, next});
        }
    }
    ret.erase(ret.begin());
    cout << ret.size() << "\n";
    for (pii cur : ret)
        cout << cur.first << " " << cur.second << "\n";
    return 0;
}

풀이

각자의 방식대로 채택된 노드와 그 노드의 부모를 기록하면 된다.

이후 모든 탐색이 끝났다면 해당 경로를 출력하면 된다.