[C++] 최소비용 구하기 2 (백준 11779번)

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

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int MAX_SIZE = 1000000000;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n + 1);
    vector<int> dst(n + 1, MAX_SIZE);
    vector<int> route(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
    }

    int s, e;
    cin >> s >> e;

    priority_queue<pair<int, int>> q;
    q.emplace(0, s);
    dst[s] = 0;

    while (!q.empty()) {
        int cost = -q.top().first;
        int cur = q.top().second;
        q.pop();

        if (cost > dst[cur]) continue;

        for (auto nxt: g[cur]) {
            if (cost + nxt.second < dst[nxt.first]) {
                dst[nxt.first] = cost + nxt.second;
                q.emplace(-dst[nxt.first], nxt.first);
                route[nxt.first] = cur;
            }
        }
    }

    vector<int> ans;
    int idx = e;
    while (idx != s) {
        ans.push_back(idx);
        idx = route[idx];
    }
    ans.push_back(idx);

    cout << dst[e] << '\n' << ans.size() << '\n';
    for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << ' ';
    cout << '\n';
}

다익스트라 기본 + 경로 추적 문제이다. 

다익스트라는 우선 순위 큐로 거리가 짧은 것부터 꺼내면서 그걸 거쳐서 갔을 때 비용이 절약되면 계속 갱신해주는 식으로 구현하면 된다. 

경로 추적은 비용을 갱신할 때 그 노드의 직전 노드를 저장해주면 마지막에 마지막 노드에서부터 처음 노드로 역추적 할 수 있다. 

주의할 점은 if (cost > dst[cur]) continue; 이 코드가 없으면 시간 초과를 받는다. 

(AC)