BOJ 10217: KCM Travel

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (76/187)
  • 어찌보면 평범한 Knapsack. 다만 그래프기 때문에 bottom-up으로 풀긴 어려워 보인다.
  • 다익스트라랑 접목하면 빠르게 풀 수 있다고 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int N, M, K;
struct Edge {
  int v, cost, dist;
};
vector<vector<Edge>> adj;
vector<vector<int>> dp;

int go(int last, int cost) {
  if(last == N) return 0;
  if(dp[last][cost] != -1)
    return dp[last][cost];

  int ans = 1e9;
  for(Edge& e: adj[last]) {
    if(cost + e.cost > M) continue;
    int dist = go(e.v, cost + e.cost);
    if(dist == 1e9) continue;
    ans = min(ans, dist+e.dist);
  }
  return dp[last][cost] = ans;
}


int main() {
  int TC;
  scanf("%d", &TC);
  while(TC--) {
    scanf("%d %d %d", &N, &M, &K);
    adj = vector<vector<Edge>>(N+1);
    dp = vector<vector<int>>(N+1, vector<int>(M+1, -1));
    for(int i = 0; i < K; i++) {
      int u, v, c, d;
      scanf("%d %d %d %d", &u, &v, &c, &d);
      adj[u].push_back({v,c,d});
    }

    int ans = go(1,0);
    if(ans == 1e9) printf("Poor KCM\n");
    else printf("%d\n", ans);
  }
}