문제

2211번: 네트워크 복수

풀이

최소 스패닝 트리를 구하는 것인지, 다익스트라 최단 경로를 구하는 것인지 헷갈렷지만
슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다. 라는 조건 때문에 다익스트라 최단경로를 구하는 것을 알았다.
슈퍼 컴퓨터에서 다른 모든 컴퓨터까지의 최단 경로를 구해야 한다.

다익스트라 알고리즘은 최단 경로까지의 거리를 구하는 알고리즘이라 경로를 구하기 위해서는 별도의 작업이 필요하다.
다익스트라로 찾아낸 경로는 결국 출발지점을 루트로 하는 트리이다. 따라서 최단 경로를 찾을 때마다 각 노드간의 부모-자식 관계를 저장하여 경로를 알아낼 수 있다.

또한 트리이므로 N개의 노드가 있을 때 간선의 개수는 항상 N-1 이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int n, m;
vector<vector<struct Edge>> graph;
vector<int> parent;

struct Edge
{
    int dest;
    int cost;

    bool operator>(Edge input)
    {
        return this->cost > input.cost;
    }
};

struct cmp
{
    bool operator()(int a, int b){
        return a > b;
    }
    bool operator()(Edge a, Edge b)
    {
        return a > b;
    }
};

void dijkstra(int start)
{
    priority_queue<Edge, vector<Edge>, cmp> pq;
    vector<int> dist(n+1, 10*(n-1) + 1); // 최대값 맞는지 잘 모르겟음..
    pq.push({1, 0});
    dist[1] = 0;

    while (!pq.empty())
    {
        int cur = pq.top().dest;
        int curCost = pq.top().cost;
        pq.pop();

        if (dist[cur] < curCost)
            continue;

        for (auto n : graph[cur])
        {
            int next = n.dest;
            int nextCost = curCost + n.cost;

            if (nextCost >= dist[next]) // 비용이 더 적을때만 갱신
                continue;

            dist[next] = nextCost;
            pq.push({next, nextCost});

            parent[next] = cur;
        }
    }

}

int main() 
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    graph.assign(n+1, vector<Edge>());
    parent.assign(n+1, 0);
    for (int i=0; i<m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    dijkstra(1);
    
    cout << n-1 << "\n";
    for (int i=2; i<n+1; ++i)
    {
        cout << i << " " << parent[i] << "\n";
    }

    return 0;
}