백준 11779번 : 최소비용 구하기2 - 다익스트라

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

#include <bits/stdc++.h>
using namespace std;

int n, m, st, en;

pair<int, int> dist[1001]; //거리 , 이전노드 저장 

vector<pair<int, int> > v[1001];

struct Node {
	int x, ex ,d;
	bool operator<(const Node& b)const {
		return d > b.d;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	memset(dist, 0x3f, sizeof(dist));

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b, c });
	}

	cin >> st >> en;
	priority_queue<Node> Q;
	Q.push({ st,-1,0 });

	vector<int> ans;


	while (!Q.empty()) {
		int x = Q.top().x;
		int ex = Q.top().ex;
		int d = Q.top().d;
		Q.pop();

		if (dist[x].first <= d) continue;

		dist[x].first = d;
		dist[x].second = ex;


		if (x == en) {
			int a = en;

			while (a != -1) {
				ans.push_back(a);
				a = dist[a].second;
			}

			cout << d << '\n';
			cout << ans.size() << '\n';

			for (int i = ans.size() - 1; i >= 0; i--) {
				cout << ans[i] << ' ';
			}
			return 0;
		}


		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx].first > nd) {
				Q.push({ nx,x,nd });
			}
		}
	}



	return 0;
}

백준 11779번