백준 2211번: 네트워크 복구

문제 링크 : https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

 

 

 문제 설명 

 

1. 처음에 해킹당하기 전에 연결된 네트워크가 주어짐.

2. 네트워크는 가중치가 있는 양방향 그래프 형식.

3. 최소의 가중치로 모든 네트워크를 연결 하기위한 간선의 갯수와 연결할 간선을 출력.

 

 알고리즘 

 

1. 다익스트라 알고리즘을 이용하여 통신 최소 시간 을 계속 갱신.

2. 최소 시간을 갱신하면서 따로 배열을 만들어 네트워크를 이어주는 간선 갱신

3. 출력

 

 코드 

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
typedef pair<int, int> P;
 
vector<P> V[1001];
vector<int> pos[1001];
int N, M;
int check[1001];
int line[1001];
 
 
//다익스트라 알고리즘
void dijkstra(int start) {
    check[start] = 0;
    priority_queue<P> pq;
    pq.push(P(0, start));
 
    while (!pq.empty()) {
        int curr = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();
 
        if (dist < check[curr])continue;
 
 
        for (int i = 0; i < V[curr].size(); i++) {
 
            int next = V[curr][i].first;
            int next_dist = V[curr][i].second+dist;
 
            if (next_dist < check[next]) {
                check[next] = next_dist;
                pq.push(P(-next_dist, next));                
 
                //재 생성할 네트워크를 갱신.
                line[next] = curr;
 
            }
        }
 
    }
 
 
}
int main() {
    vector<P> dap;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        V[a].push_back(P(b, c));
        V[b].push_back(P(a, c));
    }
    for (int i = 0; i <= N; i++)check[i] = 100000;
    for (int i = 0; i <= N; i++)line[i] = 0;
    dijkstra(1);
    int cnt = 0;
    for (int i = 0; i <= N; i++) {
        if (line[i])cnt++;
    }
 
    cout << cnt << "\n";
    for (int i = 1; i <= N; i++) {
        if (line[i]) {
            cout << i <<" " <<line[i] << "\n";
        }
    }
 
 
}