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

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int n_ = 1e3 + 3;
const int INF = 1e9;

struct edg {
	int idx, dst;
	edg(int idx, int dst) : idx(idx), dst(dst) {}
	bool operator <(edg A)const { return dst > A.dst; }
};
int n, m, trc[n_], dst[n_];
vector<int> ans;
vector<edg> gph[n_];

int main() {
	int i, u, v, c, s, e;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &u, &v, &c);
		gph[u].push_back(edg(v, c));
	}
	scanf("%d %d", &s, &e);
	for (i = 1; i <= n; i++) dst[i] = INF;
	dst[s] = 0;
	priority_queue<edg> pq;
	pq.push(edg(s, dst[s]));
	while (!pq.empty()) {
		edg now = pq.top();
		pq.pop();
		if (now.idx == e) break;
		if (now.dst != dst[now.idx]) continue;
		for (auto nxt : gph[now.idx]) {
			if (dst[nxt.idx] > now.dst + nxt.dst) {
				dst[nxt.idx] = now.dst + nxt.dst;
				trc[nxt.idx] = now.idx;
				pq.push(edg(nxt.idx, dst[nxt.idx]));
			}
		}
	}
	int t = e;
	while (t) {
		ans.push_back(t);
		t = trc[t];
	}
	printf("%d\n%d\n", dst[e], ans.size());
	for (i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
	return 0;
}