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

문제 출처: https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

출발점과 도착점의 사이의 최소비용을 구하고 경로를 저장해놓은 뒤 도착점으로부터 역추적 하여 경로를 재구성 할 수 있음

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int>P;

vector<P> adj[1001];

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back(P(b, d));
    }
    long long INF = 123456891;
    long long dist[1001];
    fill(dist, dist + 1001, INF);
    
    int s, e;
    cin >> s >> e;
    dist[s] = 0;
    int root[1001];
    root[s] = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (P p : adj[j]) {
                int next = p.first, d = p.second;
                if (dist[j] != INF && dist[next] > dist[j] + d) {
                    root[next] = j;
                    dist[next] = dist[j] + d;
                }
            }
        }
    }

    vector <int> temp;
    temp.push_back(e);
    int prev = root[e];
    while (true) {
        if (prev != -1) {
            temp.push_back(prev);
            prev = root[prev];
        }
        else break;
    }

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