최소비용 구하기 2

문제 링크

발상 & 풀이

문제를 읽어보면 매우 매우 전형적인 Dijkstra 문제라는 걸 알 수 있다. 사실 BFS 최단거리 문제들은 모두 Dijkstra 알고리즘을 기본 베이스로 한다. 지금까지의 문제들과 마찬가지로 현재 정점에 방문하기 이전의 정점을 기록하는 것으로 역추적할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct eg {
	int s, e, v, cnt, p;
};
struct cmp {
	bool operator() (eg a, eg b) {
		return a.v > b.v;
	}
};
void printpath(int c, vector<eg>& dp) {	
	if (dp[c].p == -1) {
		cout << c << " ";
		return;
	}
	printpath(dp[c].p, dp);
	cout << c << " ";
}
int main()
{
	int n, m; cin >> n >> m; vector<vector<eg>> arr(n + 1); vector<eg> dp(n + 1, { -1, -1, (int)21e8, -1, -1 });
	for (int i = 1; i <= m; i++) {
		int s, e, v; cin >> s >> e >> v;
		arr[s].push_back({ s, e, v, -1, -1 });
	}
	int s, e; cin >> s >> e;
	priority_queue<eg, vector<eg>, cmp> pq; pq.push({ s, s, 0, 1, -1 });
	dp[s] = { s, s, 0, -1, -1 };
	while (!pq.empty()) {
		auto cur = pq.top(); pq.pop();
		if (cur.s == e) {
			cout << cur.v << "\n" << cur.cnt << "\n";
			printpath(cur.s, dp);
			return 0;
		}
		for (auto nx : arr[cur.s]) {
			if (dp[nx.e].v > cur.v + nx.v) {				
				dp[nx.e].v = cur.v + nx.v;
				dp[nx.e].cnt = cur.cnt + 1;
				dp[nx.e].p = cur.s;
				pq.push({ nx.e, nx.e, cur.v + nx.v, cur.cnt + 1, cur.s });
			}
		}
	}
	return 0;
}