题解 | 最大价值路径动态规划加预处理

#include<iostream>
#include<vector>
#include<list>
#include<climits>

using namespace std;

struct Edge {
    int to, cost;

    Edge(int to, int cost) : to(to), cost(cost) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    int values[n + 1];
    for (int i = 1; i <= n; i++) cin >> values[i];
    vector<list<Edge>> graph(n + 1);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].emplace_back(y, z);
    }
    vector<vector<int>> dp(n + 1, vector<int>(801));
    for (int i = 0; i <= 801; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 0) dp[j][i] = values[j];
            else {
                for (const auto&[to, cost]:graph[j]) {
                    if (i >= cost && dp[j][i] < dp[to][i - cost] + values[j]) dp[j][i] = dp[to][i - cost] + values[j];
                }
            }
        }
    }
    int ans[n + 1][801];
    for (int i = 1; i <= n; i++) {
        int max = 0;
        for (int j = 0; j <= 800; j++) {
            if (dp[i][j] > max) max = dp[i][j];
            ans[i][j] = max;
        }
    }
    while (q--) {
        int u, c;
        cin >> u >> c;
        cout << ans[u][c] << endl;
    }
    return 0;
}