백준 11779번 최소비용 구하기 2 문제풀이(C++)

백준 11779번 최소비용 구하기 2

아이디어

A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로

다익스트라 알고리즘 사용

최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력

방문 순서가 2, 5, 4, 1 이라 했을 때,
배열에 arr[1] = 4, arr[4] = 5, arr[5] = 2 와 같은 방식으로 저장해서 end서부터 역순으로 출력

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000 + 5
vector<pair<int, int>> v[MAX];
vector<int> way;
int dist[MAX];
int route[MAX];
int n, m;
void dijkstra(int start, int end) {
	for (int i = 1; i <= n; i++)
		dist[i] = 2100000000;
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ start, 0 });
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = -pq.top().second;
		pq.pop();
		if (cost > dist[cur]) continue;
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int ncost = v[cur][i].second;
			if (cost + ncost < dist[next]) {
				dist[next] = cost + ncost;
				pq.push({ next, -dist[next] });
				route[next] = cur;
			}
		}
	}
	cout << dist[end] << '\n';
	int tmp = end;
	while (tmp) {
		way.push_back(tmp);
		if (tmp == start)break;
		tmp = route[tmp];
	}
	cout << way.size() << '\n';
	for (int i = (int)way.size() - 1; i >= 0; i--)
		cout << way[i] << ' ';
	cout << '\n';
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, length; cin >> start >> end >> length;
		v[start].push_back({ end, length });
	}
	int start, end; cin >> start >> end;
	dijkstra(start, end);
	return 0;
}