백준 g3 11779 최소비용 구하기 2 c++ (다익스트라 경로 복원)

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

11779번: 최소비용 구하기 2

 

문제

다익스트라인데 경로 복원하기

 

풀이

pre[노드] 배열을 둬서 경로가 업데이트 될 때마다 이전의 노드가 무엇이었는지 추가하고,

마지막에 pre[end] -> pre[start]로 따라가면 경로가 나온다.

다익스트라는 노드를 하나씩 확정시켜나가면서 확정된 노드의 인접한 노드들을 업데이트하므로,

pre[확정된 노드의 인접한 노드] = 확정된 노드로 경로 복원을 할 수 있다.

    int cost, num;
    while (!PQ.empty()) {
        tie(cost, num) = PQ.top();
        PQ.pop();

        if (dist[num] != cost) continue;

        for (pair<int, int> a : adj[num]) {
            if (dist[a.second] > dist[num] + a.first) {
                dist[a.second] = dist[num] + a.first;
                (*) pre[a.second] = num; 
                PQ.push({dist[a.second], a.second});
            }
        }
    }

 

 

전체 코드

/*boj g3 11779 최소비용 구하기 2 (다익스트라 경로 복원)*/
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define MAXN 1005
#define INF 1e9 + 10
using namespace std;

int N, M;
int sn, en;
vector<pair<int, int>> adj[MAXN]; // 비용, 노드 번호
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;
int dist[MAXN];
int pre[MAXN];
vector<int> route;
void input() {
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({w, v});
    }
    cin >> sn >> en;
}

void initialize() {
    for (int i = 0; i <= MAXN; i++) {
        dist[i] = INF;
    }
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    initialize();

    // 1. 시작점 넣기
    dist[sn] = 0;
    PQ.push({0, sn});
    pre[sn] = -1;
    // 2. 다익스트라 진행
    int cost, num;
    while (!PQ.empty()) {
        tie(cost, num) = PQ.top();
        PQ.pop();

        if (dist[num] != cost) continue;

        for (pair<int, int> a : adj[num]) {
            if (dist[a.second] > dist[num] + a.first) {
                dist[a.second] = dist[num] + a.first;
                pre[a.second] = num;
                PQ.push({dist[a.second], a.second});
            }
        }
    }

    // 경로 복원
    route.push_back(en);
    int cur = en;
    while (cur != sn) {
        cur = pre[cur];
        route.push_back(cur);
    }
    // 출력
    cout << dist[en] << "\n";
    cout << route.size() << "\n";

    for (int i = route.size() - 1; i >= 0; i--) {
        cout << route[i] << " ";
    }
    cout << "\n";
}