11779 - 최소비용 구하기

다익스트라에서 dist 배열을 갱신할 때 마다 parent 배열에 연결된 노드를 저장하면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#define INF 0x7fffffff;
using namespace std;

vector<pair<int, int>> adj[1001];
// 최소 비용 저장
int dist[1001];
// 최소 비용을 갖는 부모 저장
int parent[1001];
// 경로에 포함된 도시 경로 개수
int cnt;
bool visited[1001];
void dijkstra(int root) {
	dist[root] = 0;
	priority_queue<pair<int, int>> q;
	q.push({ 0, root });
	while (!q.empty()) {
		int now = q.top().second; q.pop();
		if (visited[now]) continue;
		visited[now] = true;
		for (auto p : adj[now]) {
			int next = p.first;
			int w = p.second;
			if (w + dist[now] < dist[next]) {
				dist[next] = w + dist[now];
				parent[next] = now;
				cnt++;
				q.push({ -dist[next], next });
			}
		}
	}
}
int main()
{
	int N, M;
	cin >> N >> M;
	int s, e;
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
	for (int m = 0; m < M; m++) {
		int u, v, x;
		cin >> u >> v >> x;
		adj[u].push_back({ v, x });
	}
	cin >> s >> e;
	dijkstra(s);
	printf("%d\n", dist[e]);
	stack<int> st;
	while (e != 0) {
		st.push(e);
		e = parent[e];
	}
	printf("%d\n", st.size());
	while (!st.empty()) {
		printf("%d ", st.top());
		st.pop();
	}
}