백준 2211:네트워크 복구

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

백준 2211번 다익스트라 관련 문제예요. 기본 최소비용탐색 문제에서 회선 정보만 빼오면 되는거예여. prev배열을 만들어서 현재노드와 전 노드를 연결하는 회선 정보를 저장해요. -1이라면 회선이 없는 것. 갯수를 카운팅 해주고 회선 정보를 출력하면 되요.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
#define INF (static_cast<int>(1e9))
#define endl '\n'
 
typedef pair<int, int> PAIR;
int main(void) {
    ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
    vector<vector<PAIR>> computer(N);
    vector<bool> visited(N);
    vector<int> cost(N, INF);
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
 
    for (int i = 0; i < M; i++) {//양방향 그래프 입력요
        int A, B, C; cin >> A >> B >> C;
        computer[A - 1].push_back(PAIR(B - 1, C));
        computer[B - 1].push_back(PAIR(A - 1, C));
    }
    
    pq.push(PAIR(0, 0));
    cost[0] = 0;//시작점은 0
    
    vector<int> prev(N, -1);
    //prev배열은 이전노드와 현재노드를 연결해요
    //나중에 회선을 출력할때 유용해요 / 초기값을 -1(없는 값)로 했어요
    while (!pq.empty()) {
        int cur;//다익스트라 알고리즘
        do {
            cur = pq.top().second; pq.pop();
        } while (!pq.empty() && visited[cur]);
 
        if (visited[cur]) break;
        visited[cur] = true;
        
        for (auto& i : computer[cur]) {
            int next = i.first, time = i.second;
            if (cost[next] > cost[cur] + time) {
                cost[next] = cost[cur] + time;
                pq.push(PAIR(cost[next], next));
                prev[next] = cur;
                //거리 갱신하면서 이어진 회선을 저장해요
            }
        }
    }
    int cnt = 0;//회선 갯수
    for (const int& i : prev) {
        if (i != -1) cnt++;
        //-1이 아니라면 회선이 있는거예요!
    }
    cout << cnt << endl;
    for (int i = 0; i < N; i++) {
        if (prev[i] != -1) {
            cout << prev[i] + 1 << ' ' << i + 1 << endl;
        }//회선 정보를 출력해요
    }
 
    return 0;
}