Codeforces Round 857 (Div. 1) - D. The way home (2100)

D. The way home

$n \le 800$ 을 관찰하여 $dp[i][j]=i$ 번째 노드에서 지금까지 거친 경로중 가장 $w$가 큰 노드가 $j$ 일 때 (최소 공연 횟수, 최대로 남은 돈) 을 저장하여 다익스트라를 돌리는 문제이다.

다음은 내가 문제를 풀며 했던 관찰이다.

올바르게 문제에 접근했다.

• 최단경로까지 p이하의 돈으로 갈 수 있으면 정답은 0
• 항상 w[i] 가 가장 높은 도시에서 performance를 진행한다.
• 최단경로로 가는것이 정답이 아닐 수 있다.
• 지금까지 거쳐 온 경로중에 가장 w가 큰 것에서 현재 공연을 한다고 가정할 수 있다.
• $dp[i][j] = i$ 번째 정점에서 현재 지나온 정점 중 w의 최대를 가진 정점이 j일 때 (최소 공연, 최대 돈)

이 pair는 그저 대소관계를 따져주면 된다.

단순히 < 로 처리하려면 최대 돈을 음수로 처리해주고 다익스트라를 돌리면 된다.

그래프에서 간선은 현재 $(i, j)$ 라면 $(nxt, ?)$ 가 되는데, 만약 $w_j < w_{nxt}$ 라면 $?$는 $nxt$가 될 것이고 아니라면 $j$ 가 된다.

시간복잡도는 정점이 $O(n^2)$ 개 있고 간선이 $O(nm)$ 개 있기 때문에 다익스트라로 $O(nm \log n^2)$ 정도로 풀리는 듯 하다.

const int inf = 2e16;
void solve() {
   int n, m, p;
   cin >> n >> m >> p;
   vi w(n);
   fv(w);
   vector<vector<pi>> edges(n);
   for (int i = 0, u, v, s; i < m; i++) cin >> u >> v >> s, u--, v--, edges[u].pb({v, s});
   vector<vector<pi>> dp(n, vector<pi>(n, {inf, -inf}));
   dp[0][0] = {0, -p};
   // 최소 공연, 최대 돈, 인덱스, best
   priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq;
   pq.push({0, -p, 0, 0});
   while (sz(pq)) {
      auto [show, money, cur, big_w] = pq.top();
      pq.pop();
      money *= -1;
      if (cur == n - 1) continue;
      if (mp(dp[cur][big_w].fi, -dp[cur][big_w].se) < mp(show, -money)) continue;
      for (const auto &[to, s]: edges[cur]) {
         int nxt_big_w = w[big_w] > w[to] ? big_w : to;
         int show_need = (max(0ll, s - money) + w[big_w] - 1) / w[big_w];
         if (mp(dp[to][nxt_big_w].fi, -dp[to][nxt_big_w].se)
            > mp(show + show_need, -(money + show_need * w[big_w] - s))) {
            dp[to][nxt_big_w] = mp(show + show_need, money + show_need * w[big_w] - s);
            pq.push({dp[to][nxt_big_w].fi, -dp[to][nxt_big_w].se, to, nxt_big_w});
         }
      }
   }
   int ans = inf;
   for (int i = 0; i < n; i++) {
      if (dp[n - 1][i].fi == inf) continue;
      mina(ans, dp[n - 1][i].fi);
   }
   if (ans == inf) cout << -1 << endl;
   else cout << ans << endl;
}