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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
vector<pii> v[1001];
int dist[1001];
int pre[1001];
int n, m;
int s, e;
int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	memset(pre, -1, sizeof(pre));
	for (int i = 1; i <= n; i++) {
		dist[i] = 2e9;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	cin >> s >> e;
	priority_queue<pii, vector<pii> > pq;
	dist[s] = 0;
	pq.push({ 0,s });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();

		for (auto nxt : v[node]) {
			int next = nxt.first;
			int cost = nxt.second;
			
			if (dist[next] > dist[node] + cost) {
				dist[next] = dist[node] + cost;
				pre[next] = node;
				pq.push({ -dist[next],next });
			}
		}
	}
	stack<int> path;
	for (int i = e; i != -1; i = pre[i]) {
		path.push(i);
	}
	cout << dist[e] << "\n";
	cout << path.size() << "\n";
	while (!path.empty()) {
		cout << path.top() << " ";
		path.pop();
	}

	
}