10217 KCM Travel

์•Œ๊ณ ๋ฆฌ์ฆ˜(๋‹ค์ต์ŠคํŠธ๋ผ, DP)

1. ๊ธฐ๋ณธ์ ์œผ๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ตœ์†Œ๊ฒฝ๋กœ๋ฅผ ์ฐพ์•„์•ผํ•˜๋Š” ๊ฒƒ์„ ๋งž์œผ๋‚˜, ๋น„์šฉ์ด ๋„˜์–ด๋ฒ„๋ฆด๊ฒฝ์šฐ ์ด์ „์˜ ์ตœ์†Œ๊ฒฝ๋กœ๋กœ ๊ฐ„ ๊ฒƒ์ด ์˜๋ฏธ๊ฐ€ ์—†์–ด์ง„๋‹ค.
   ๋”ฐ๋ผ์„œ ํ˜„์žฌ ํ์—์„œ ๊บผ๋‚ธ ๋…ธ๋“œ๊ฐ€, ์ด์ „์— ์ง€๋‚˜๊ฐ„ ๋…ธ๋“œ๋ณด๋‹ค ๊ฐ™์€ ๋น„์šฉ์ผ๋•Œ ๋” ์‹œ๊ฐ„์ด ๋งŽ์ด ๊ฑธ๋ ธ์„ ๊ฒฝ์šฐ๋งŒ ํŒจ์Šค.
  DP[101][10001] ์„ ์–ธ
2. ์ฒซ๋ฒˆ์งธ๋ฅผ ์ œ์™ธํ•˜๊ณ , ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ INF ๋กœ ์ดˆ๊ธฐํ™”
3. ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด์„œ, ํ˜„์žฌ ํ์—์„œ ๊บผ๋‚ธ ๋…ธ๋“œ์˜ ์‹œ๊ฐ„์ด DP[ํ˜„์žฌ๋…ธ๋“œ][ํ˜„์žฌ๋…ธ๋“œ์˜ ๋น„์šฉ] ๋ณด๋‹ค ํด ๋•Œ ํŒจ์Šค (๊ฐ™์€ ๊ฑฐ๋Š” ํ˜„์žฌ ์ผ ์ˆ˜ ์žˆ์Œ)
4. ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ์—…๋ฐ์ดํŠธํ• ๋•Œ, (๋‹ค์Œ๋…ธ๋“œ๋กœ ๊ฐ€๋Š”๋น„์šฉ ~ ์ตœ๋Œ€๋น„์šฉ) ๊นŒ์ง€ ์ด๋ฏธ ์ €์žฅ๋œ ๊ฐ’๋ณด๋‹ค ์ž‘์„ ๋•Œ DP[๋‹ค์Œ๋…ธ๋“œ][๋น„์šฉ] ์„ ๋‹ค์Œ ์‹œ๊ฐ„์œผ๋กœ ์—…๋ฐ์ดํŠธ

์ฝ”๋“œ

#include <bits/stdc++.h>
#define INF 2000000000
 
using namespace std;
 
struct Line {
	int to;
	int m;
	int time;
};
 
vector<Line> airport[101];
int N, M, K, DP[101][10001];
queue<Line> q;
 
void dijkstra();
void init() {
	for (int i = 1; i <= N; i++) {
		airport[i].clear();
		for(int j = 1; j<=M; j++)
			DP[i][j] = INF;
 	}
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		cin >> N >> M >> K;
		init();
 
		for (int j = 0; j < K; j++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			airport[a].push_back({ b, c, d });
		}
 
		dijkstra();
 
		int answer = INF;
		for (int j = 1; j <= M; j++)
			answer = min(answer, DP[N][M]);
 
		if (answer == INF)
			cout << "Poor KCM" << "\n";
		else
			cout << answer << "\n";
	}
}
 
void dijkstra() {
	q.push({1, 0, 0});
 
	while (!q.empty()) {
		Line a = q.front();
		q.pop();
 
		if (a.time > DP[a.to][a.m])
			continue;
 
		for (int j = 0; j < airport[a.to].size(); j++) {
			Line next = airport[a.to][j];
			int nm = a.m + next.m, nt = a.time + next.time, to = next.to;
 
			if (nm <= M && nt < DP[to][nm]) {
				q.push({ to, nm, nt });
				for (int k = nm; k <= M; k++)
					if(nt < DP[to][k])
						DP[to][k] = nt;
			}
		}
	}
}