[BOJ] 11779번: 최소비용 구하기 2

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

다익스트라를 구현하는데 경로를 저장해야 한다. 

추적방법

1. trace 배열을 선언한다.
2. 다익스트라 알고리즘에서 거리 업데이트하는 부분에 trace[nxt.idx] = now.idx로 지정한다.
3. 도착 지점부터 trace 배열을 돌면서 t = trace[t]를 통해 노드 A로 오기 전 노드로 t를 변경한다.

#include <bits/stdc++.h>
using namespace std;

struct Edg {
    int idx, fair;
    Edg(int i, int f) : idx(i), fair(f) {}
    bool operator<(const Edg& a) const { return a.fair < fair; }
};

int N, M, From, To, dist[1001], trace[1001];
vector<Edg> v[1001];

int main()
{
    memset(dist, 0x3f, sizeof dist);
    scanf("%d %d", &N, &M);
    for (int i = 0, f, t, w; i < M; ++i) {
        scanf("%d %d %d", &f, &t, &w);
        v[f].push_back({ t, w });
    }
    scanf("%d %d", &From, &To);

    dist[From] = 0;
    priority_queue<Edg> pq;
    pq.push({ From, 0 });

    while (!pq.empty()) {
        auto now = pq.top();
        pq.pop();

        if (now.fair != dist[now.idx]) continue;

        for (auto& nxt : v[now.idx]) {
            if (dist[nxt.idx] > nxt.fair + now.fair) {
                dist[nxt.idx] = nxt.fair + now.fair;
                trace[nxt.idx] = now.idx;
                pq.push({ nxt.idx, dist[nxt.idx] });
            }
        }
    }
    vector<int> ans;
    int tmp = To;
    while (tmp) {
        ans.push_back(tmp);
        tmp = trace[tmp];
    }
    printf("%d\n%d\n", dist[To], ans.size());
    for (int i = (int)ans.size() - 1; i >= 0; --i)
        printf("%d ", ans[i]);
    
    return 0;
}