2211번

2211번 - 네트워크 복구

다익스트라를 이용해서 최단 거리를 구하면 된다.

슈퍼컴퓨터로 부터 모든 노드들의 최단거리를 구하면 주어진 조건에 맞게 된다.

그리고 BFS,다익스트라,벨만포드는 전부 parent 배열을 만들어서 , 

dist 값이 갱신될 때 parent 값들을 넣어주면 실제 경로를 구할 수 있다.

몇몇 사람들은 MST ( 최소 스패닝 트리) 로 접근한 사람들도 있는데... 2번 조건 때문에 안되는 것 같다.

모든 노드들의 합이 최소라고 해서, 그 노드들이 슈퍼컴퓨터로 부터 최단거리로 연결한다고 보장할 수 없기 때문이다?

사실 정확히 확신은 안가지만, 다익스트라로 확실히 풀 수 있다.

##추가로

밑에 코드에서 ans를 통해 간선의 갯수를 구했는데..

n개의 정점에서 최소의 간선은 n-1입니다.(신장트리)    라고 한다...

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF = 987654321;
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    vector<vector<pair<int,int>>> v(n + 1);
    vector<int> dist(n + 1,INF);
    vector<int> parent(n + 1,-1);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
 
    priority_queue<pair<int, int>> q;
    dist[1] = 0;
    q.push({ 1,dist[1] });
 
    while (!q.empty())
    {
        int now = q.top().first;
        int cost = -q.top().second;
        q.pop();
 
        if (cost > dist[now]) { continue; };
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[next] > cost + w)
            {
                dist[next] = cost + w;
                parent[next] = now;
                q.push({ next,-dist[next] });
            }
        }
    }
    int ans = 0;
 
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] < INF && parent[i] !=-1)
        {
            ans++;
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] < INF && parent[i] != -1)
        {    
            printf("%d %d\n" ,i, parent[i]);
        }
    }
 
    return 0;
}