[Algorithm]Baekjoon 2211번 :: 네트워크 복구

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
struct Node
{
    int node;
    int dist;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.dist > b.dist;
    }
};
 
int n, m;
vector<vector<Node>> graph(1001);
int dist[1001] = { 0 };
int parent[1001] = { 0 };
const int maxNum = 0x3f3f3f3;
 
void Dij(int startNode)
{
    vector<pair<int, int>> edges;
    int lineCount = 0;
 
    dist[startNode] = 0;
 
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ startNode,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curDist = pq.top().dist;
 
        pq.pop();
 
        if (dist[curNode] < curDist) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextDist = curDist + graph[curNode][i].dist;
 
            if (nextDist < dist[nextNode]) // 새로업데이트하는거라면
            {
                parent[nextNode] = curNode;
                dist[nextNode] = nextDist;
                pq.push({ nextNode,nextDist });
            }
        }
    }
 
    printf("%d\n", n - 1);
    for (int i = 2; i <= n; ++i)
    {
        printf("%d %d\n", i, parent[i]);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    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 });
    }
    
    memset(dist, 0x3f, sizeof(dist));
 
    Dij(1);
}
 
 

 

 

문제의 포인트는, 1번정점부터 시작해서 최소비용으로 모든 정점 돌았을 때, 각 간선의 정보를 구해야한다는 것이다.

복구회선은 무조건 n-1개이다. 최소비용이기 때문에 각 정점을 잇는 회선 1개씩만 구성되어지기 때문이다.

 

간선의 정보는, 새로운 거리를 업데이트할 때 부모자식관계를 저장함으로써 구한다. (63번째 라인)