[11779] 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

<문제>

경로가 갱신될때마다 이전 노드를 저장한다면, e에서 s까지 역으로 경로를 복원할 수 있다.

물론, 이렇게 만들어진 경로는 도착->출발 순서이므로, 필요에 따라 reverse해주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX_N = 100'000, INF = (ll)1e17;

ll n, m, s, e, dst[MAX_N + 1], path[MAX_N + 1];
typedef struct {
    ll idx, cost;
} state;
vector<state> adj[MAX_N + 1];

void dijkstra(ll s) {
    auto cmp = [&](state& A, state& B) -> bool { return A.cost > B.cost; };
    priority_queue<state, vector<state>, decltype(cmp)> q(cmp);
    q.push({s, 0});
    fill(dst, dst + MAX_N + 1, INF);
    dst[s] = 0;

    while (!q.empty()) {
        state cur = q.top();
        q.pop();
        if (cur.cost > dst[cur.idx]) continue;

        for (auto& nxt : adj[cur.idx]) {
            if (dst[nxt.idx] > dst[cur.idx] + nxt.cost) {
                dst[nxt.idx] = dst[cur.idx] + nxt.cost;
                q.push({nxt.idx, dst[nxt.idx]});
                path[nxt.idx] = cur.idx;
            }
        }
    }
    return;
}
void findPath(vector<ll>& ret) {
    ll cur = e;
    path[s] = -1;
    for (;; cur = path[cur]) {
        if (cur <= 0) break;
        ret.push_back(cur);
    }
    reverse(ret.begin(), ret.end());
    return;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    ll i;
    for (i = 0; i < m; i++) {
        ll A, B, C;
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
    }
    cin >> s >> e;
    dijkstra(s);
    cout << dst[e] << '\n';
    vector<ll> ret;
    findPath(ret);
    cout << ret.size() << '\n';
    for (auto& i : ret) cout << i << ' ';
    return 0;
}