[BOJ] 백준 10217번: KCM Travel

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

10217번: KCM Travel

M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다.

DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸 고려하지못해서 3번이나 틀렸습니다..)

dp[i][j] 는 i 도시의 티켓 정보 중 j+cost가 m원 이하인 티켓 중 최소 소요시간을 찾아가면 됩니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <math.h>
#include <memory.h>
#include <set>
using namespace std;

struct ticket {
	int destination;
	int cost;
	int time;
};

int n, m, k;
int dp[101][10001]; // i번 도시까지 j원으로 가는 경우 걸리는 시간
int buf[101][101][2];
vector<ticket> v[101];

int recv(int node, int money) {
	if (money > m) {
		return 1e7;
	}
	if (node == n) {
		return 0;
	}
	int& ret = dp[node][money];
	if (~ret) return ret;
	ret = 1e7;
	for (auto nxt : v[node]) {
		ret = min(ret, recv(nxt.destination, money + nxt.cost) + nxt.time);
	}
	return ret;
}
void solve() {
	memset(dp, -1, sizeof(dp));
	memset(buf, 0, sizeof(buf));
	cin >> n >> m >> k;
	for(int i = 1; i <= n ; i++){
        v[i].clear();
    }
	for (int i = 0; i < k; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		ticket info = { b,c,d };
		v[a].push_back(info);
	}
	int ans = recv(1, 0);
	if (ans >= 1e7 || ans == -1) {
		cout << "Poor KCM";
	}
	else {
		cout << ans;
	}

	cout << "\n";

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}