[백준/C++][네트워크 복구(2211번)]

문제

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

2211번: 네트워크 복구

문제 해결

1. 인접 리스트로 데이터들을 받는다.

2. 다익스트라 알고리즘을 실행한다.

3. 다익스트라 알고리즘에서 만약 new_val이 더 작으면 trace배열의 trace[next_node] = node 로 해준다.

4. 이렇게 해주면 해당노드의 최단거리의 부모를 알 수 있다.

5. trace배열을 각 노드들 별로 출력해준다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define max 1001
#define infy 98765432
using namespace std;
int N,M;
int dist[max];
vector <pair<int,int>> adj[max];
int trace[max];
void set(void){
    for(int i = 0;i<=N;i++){dist[i] = infy;}
}
void dijkstra(int node){
    priority_queue<pair<int,int>> pq;
    pq.push(make_pair(0,node));
    while(!pq.empty()){
        node = pq.top().second;
        pq.pop();
        int cost = pq.top().first;
        if(cost>dist[node]){continue;}
        for(int i = 0;i<adj[node].size();i++){
            int next_node = adj[node][i].first;
            int new_val = adj[node][i].second+dist[node];
            int before_val = dist[next_node];
            if(new_val<before_val){
                dist[next_node] = new_val;
                pq.push({-1*new_val,next_node});
                trace[next_node] = node;
            }
        }
    }
}
void solve(void){
    cout << N-1 << "\n";
    for(int i = 2;i<=N;i++){
        cout << trace[i] << " " << i <<"\n"; 
    }
}
int main(void){
    cin >> N >> M;
    for(int i = 0;i<M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }
    set();
    dist[1] = 0;
    dijkstra(1);
    solve();
}