BOJ 10776 - 제국

BOJ 10776 - 제국

개인적으로 고평가 되어있는 문제인데, $D_{i,h}$ 를 $i$번 정점에 체력 $h$를 가지고 도달하는 최단 시간이라고 한다면 $N \le 2,000$ 이고 $K \le 200$ 이기 때문에 단순히 BFS를 돌리는 것만으로 특별한 전처리없이 정답을 구할 수 있다.

const int inf = 2e9;
void solve() {
   int k, n, m, a, b;
   cin >> k >> n >> m;
   vvi dist(n, vi(k + 1, inf));

   vector<vector<array<int, 3>>> edges(n);
   while (m--) {
      int a, b, t, h;
      cin >> a >> b >> t >> h;
      a--, b--;
      edges[a].pb({b, t, h});
      edges[b].pb({a, t, h});
   }

   cin >> a >> b, a--, b--;
   dist[a][k] = 0;
   queue<pi> q;
   q.push({a, k});
   int ans = 1e9;
   while (sz(q)) {
      auto [cur, hp] = q.front();
      q.pop();
      if (cur == b) {
         mina(ans, dist[cur][hp]);
         continue;
      }
      for (auto &[to, t, h]: edges[cur]) {
         if (hp - h > 0 && dist[to][hp - h] > dist[cur][hp] + t) {
            dist[to][hp - h] = dist[cur][hp] + t;
            q.push({to, hp - h});
         }
      }
   }
   if (ans == 1e9) cout << -1;
   else cout << ans;
}