P9504 题解

Register_int · 2023-08-06 16:02:29 · 题解

绷不住了。

题面给出了 w\le100 的限制，就说明，只要我们起始状态的魔力值 \ge 100 都无法影响到生命值。考虑倒着从 t 走到 s，那么步数在 100 以上的都是白走。

考虑 dp。设 dp_{u,k} 表示走到 u 点用 k 步生命值的最小值，那么有：

大力就做完了。复杂度 O((\max w)(n+m))。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e4 + 10;

vector<pair<int, int>> g[MAXN];

int n, m, s, t; ll dp[2][MAXN], ans;

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(dp[0], 0x3f, sizeof dp[0]);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    dp[0][t] = 0, ans = LLONG_MAX; 
    for (int i = 1; i <= 100; i++) {
        memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
        for (int u = 1; u <= n; u++) {
            for (auto x : g[u]) {
                int v = x.first, w = x.second;
                dp[i & 1][u] = min(dp[i & 1][u], dp[~i & 1][v] + w / i);
            }
        }
        ans = min(ans, dp[i & 1][s]);
    }
    printf("%lld", ans);
}