[BOJ 10217] KCM Travel

문제

BOJ 10217 KCM Travel

유형

• 다익스트라 알고리즘

풀이

기존 다익스트라 알고리즘을 이용한 최단 경로 문제에서 거리 뿐만 아니라 비용에 제한이 있는 문제였다. 그래서 최단 거리를 저장한 배열이 1차원이 아닌 2차원 배열로 설정하여 풀이하였다.

dist[now][cost] 현재 위치(now)까지 사용한 비용(cost)일 때 최단 거리를 저장함
그 이외에는 다익스트라 알고리즘과 동일하다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, k, t;
struct info { int from, cost, time; };

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		vector<info> arr[101];
		for (int i = 0; i < k; i++) {
			int a, b, c, d; cin >> a >> b >> c >> d;
			arr[a].push_back({ b, c, d });
		}

		vector<vector<int>> dist(101, vector<int>(10001, INT32_MAX)); // dist[now][cost]
		dist[1][0] = 0;
		priority_queue<pair<int, pair<int, int>>> pq; // 소요시간 사용한비용 현재위치
		pq.push({ 0, {0, 1} });
		while (!pq.empty()) {
			int now = pq.top().second.second;
			int time = -pq.top().first;
			int cost = pq.top().second.first;
			pq.pop();

			if (time > dist[now][cost]) continue;

			for (auto x : arr[now]) {
				int next = x.from;
				int ntime = x.time;
				int ncost = x.cost;
				if (dist[next][cost + ncost] > dist[now][cost] + ntime && cost + ncost <= m) {
					dist[next][cost + ncost] = dist[now][cost] + ntime;
					pq.push({ -dist[next][cost + ncost], {cost + ncost, next} });
				}
			}
		}

		int ans = INT32_MAX;
		for (int i = 0; i <= 10000; i++) {
			ans = min(ans, dist[n][i]);
		}

		if (ans == INT32_MAX) cout << "Poor KCM\n";
		else cout << ans << '\n';
	}

	return 0;
}