백준 10217 KCM Travel (c++) : 피너클

10217번: KCM Travel

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

 

dp로 풀었다.

 

int n, m, k;
vector<pair<int, pair<int, int>>> graph[101];
int cache[101][10001];

사용할 변수들이다.

 

	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> n >> m >> k;
		graph->clear();
		memset(cache, -1, sizeof(cache));
		for (int i = 0; i < k; i++) {
			int u, v, c, d;
			cin >> u >> v >> c >> d;
			graph[u].push_back({ v, {c, d} });
		}
		int s = solve(1, m);
		if (s == 987654321) cout << "Poor KCM" << '\n';
		else cout << s << '\n';
	}

main에서 돌리는 것들이다.

graph는 매번 초기화 해주고 cache도 -1로 초기화 해준뒤 graph를 입력받는다.

 

solve(1, m)을 s에 넣고 만약 s가 987654321이면 도달하지 못했다는 의미이니 Poor KCM을

아니라면 s를 그대로 출력한다.

 

int solve(int now, int last_cost) {

solve함수는 (현재 정점, 현재 남은 여행비)를 매개 변수로 받고

n까지 가는데 드는 최소 거리를 반환한다.

 

int solve(int now, int last_cost) {
	if (now == n) return 0;

현재 정점이 n이면 0을 반환한다.

	int& ret = cache[now][last_cost];
	if (ret != -1) return ret;

cache를 가져와 -1이 아니면 다른 값이 채워졌다는 의미이니 ret을 반환한다.

	int time = 987654321;

	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i].first;
		int next_cost = graph[now][i].second.first;
		int next_dist = graph[now][i].second.second;

time은 now에서 n까지 가는데 걸리는 거리를 넣을 변수이다.

graph[now]와 연결된 정점들을 전부 확인하며

		if (last_cost - next_cost >= 0) {
			time = min(time, solve(next, last_cost - next_cost) + next_dist);
		}
	}

남은 여행비에서 다음 정점으로 가는 여행비를 뺀 값이 0이상이라면 solve를 돌려준다.

	return ret = time;
}

그리고 리턴하면 끝이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, m, k;
vector<pair<int, pair<int, int>>> graph[101];
int cache[101][10001];

int solve(int now, int last_cost) {
	if (now == n) return 0;
	
	int& ret = cache[now][last_cost];
	if (ret != -1) return ret;
	

	int time = 987654321;

	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i].first;
		int next_cost = graph[now][i].second.first;
		int next_dist = graph[now][i].second.second;

		if (last_cost - next_cost >= 0) {
			time = min(time, solve(next, last_cost - next_cost) + next_dist);
		}
	}

	return ret = time;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> n >> m >> k;
		graph->clear();
		memset(cache, -1, sizeof(cache));
		for (int i = 0; i < k; i++) {
			int u, v, c, d;
			cin >> u >> v >> c >> d;
			graph[u].push_back({ v, {c, d} });
		}
		int s = solve(1, m);
		if (s == 987654321) cout << "Poor KCM" << '\n';
		else cout << s << '\n';
	}
}

전체코드다.