[알고리즘] 백준 11779 - 최소비용 구하기 2 (C++)

[문제 링크] : https://www.acmicpc.net/problem/11779

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

int N, M;
vector<pair<int, int>> V[1001];
vector<int> R;
int Dist[1001];
int Route[1001];
int S, E;

void solve(){
    priority_queue<pair<int, int>> PQ;
    PQ.push({0, S});
    Dist[S] = 0;

    while(PQ.empty() == false){
        int cnt = -PQ.top().first;
        int cur = PQ.top().second;
        PQ.pop();

        if(Dist[cur] < cnt) continue;

        for(auto at : V[cur]){
            int next = at.first;
            int cost = at.second;

            if(Dist[next] > cnt + cost){
                Dist[next] = cnt + cost;
                Route[next] = cur;
                PQ.push({-Dist[next], next});
            }
        }
    }

    cout << Dist[E] << "\n";
    int tmp = E;
    while(tmp != 0){
        R.push_back(tmp);
        tmp = Route[tmp];
    }

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

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

    cin >> N >> M;
    for(int i=1; i<=N; i++){
        Dist[i] = 123456789;
    }
    int a, b, c;
    for(int i=0; i<M; i++){
        cin >> a >> b >> c;
        V[a].push_back({b, c});
    }
    cin >> S >> E;

    solve();

    return 0;
}