백준 11779 최소비용 구하기 2

#include <iostream>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;

struct Edge {
	int to;
	int cost;
	Edge(int _to, int _cost) :to(_to), cost(_cost){}
};

int N, M, a,b,c, start, dest;
bool visited[1001];
int min_cost[1001];
int starting_point[1001];
vector<Edge> graph[1001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back(Edge(b, c));
	}
	for (int i = 1; i <= N; i++)
	{
		min_cost[i] = INF;
		starting_point[i] = -1;
	}
	cin >> start >> dest;
	min_cost[start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ -min_cost[start],start });
	while (!pq.empty())
	{
		pair<int, int> cur = pq.top();
		pq.pop();
		int cur_vertex = cur.second;
		if (visited[cur_vertex])
		{
			continue;
		}
		visited[cur_vertex] = true;
		for (int i = 0; i < graph[cur_vertex].size(); i++)
		{
			Edge next = graph[cur_vertex][i];
			if (min_cost[next.to] > min_cost[cur_vertex] + next.cost)
			{
				min_cost[next.to] = min_cost[cur_vertex] + next.cost;
				pq.push({ -min_cost[next.to],next.to });
				starting_point[next.to] = cur.second;
			}
		}
	}
	cout << min_cost[dest] << '\n';
	stack<int>s;
	int prev = dest; //최종 목적지에서 start까지 역추적을 할 것이다.
	while (prev != -1)
	{
		s.push(prev);
		prev = starting_point[prev];
	}
	cout << s.size() << '\n';
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	return 0;
}