題面

題目傳送門

做法

我們從答案往后倒推，如果我們要求最多可以剩下多少錢，發現 \(T \le 10^5\) 那一定就是預處理每個點有 \(k\) 元錢能走多遠， 我們就設 \(f_{i,cost}\) 來表示從 \(i\) 開始走，花 \(cost\) 最多能走多遠，我們就可以有一個轉移：

\(f_{i,cost} = \max(f_{i,cost}, f_{j, cost - p[i]} + 從 i 處加油開始走到 j 的最遠距離)\)

給一下代碼：

    for(int cost = 0 ; cost <= n * n ; cost ++ )
        for(int i = 1 ; i <= n ; i ++ )
            if(p[i] <= cost)
                for(int j = 1 ; j <= n ; j ++ )
                    f[i][cost] = max(f[i][cost], f[j][cost - p[i]] + g[i][j]);

所以我們要再列一個輔助數組 \(g_{i,j}\) 來表示在 \(i\) 處加油后走到 \(j\) 的最遠距離，我們還是沒法一下子就求出 \(g\)， 又得再列幾個輔助輔助轉移數組的數組(bushi，考慮按位處理 \(c_i\) 對于每一位用倍增距離來維護轉移，可能有點懵，我們把他抽象化：對于每一位的 \(c_i\) 設立兩個子輔助數組 \(tmp1\) 和 \(tmp2\) ，\(tmp2\) 表示還沒有更新完的 \(g_i\)， \(tmp1\) 表示更新以后的 \(tmp2\) , 顯然有 \(tmp1_j = \max(tmp1_j, tmp2_k + dist_{k, j, u})\) 轉移一輪完 \(tmp2 = tmp1\) 最終轉移完 \(g_i = tmp2\), 其中 \(dist_{i, j, u}\) 表示從 \(i\) 到 \(j\) 走了 \(2^u\) 條邊的最長距離。

這是維護 \(g\) 的代碼：

for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j] = -1e18;
        tmp2[i] = 0;
        for(int u = 18 ; u >= 0 ; u -- )
            if(c[i] & (1 << u))
            {
                for(int j = 1 ; j <= n ; j ++ )
                    for(int k = 1 ; k <= n ; k ++ )
                    tmp1[j] = max(tmp1[j], tmp2[k] + dist[k][j][u]);
                for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j];
            }
        for(int j = 1 ; j <= n ; j ++ ) g[i][j] = tmp2[j];
    }

最后，你會發現 \(dist\) 已經不用再用其他的數組來維護了，直接倍增Floyd就好了， 下放代碼：

    for(int u = 0 ; u <= 18 ; u ++ )
        for(int i = 1 ; i <= n ; i ++ )
            for(int j = 1 ; j <= n ; j ++ )
                dist[i][j][u] = -1e18;
    for(int i = 1 ; i <= n ; i ++ ) dist[i][i][0] = 0;
    for(int i = 1 ; i <= m ; i ++ )
    {
        int a, b, l;
        cin >> a >> b >> l;
        dist[a][b][0] = max(dist[a][b][0], l);
    }
    for(int u = 1 ; u <= 18 ; u ++ )
        for(int k = 1 ; k <= n ; k ++ )
            for(int i = 1 ; i <= n ; i ++ )
                for(int j = 1 ; j <= n ; j ++ )
                    dist[i][j][u] = max(dist[i][k][u - 1] + dist[k][j][u - 1], dist[i][j][u]);

這道題目就是很經典的倒推思想，從答案推到給出的信息，倒著推很絲滑，但如果你正著推就無從下手，以上只是我的看法，大佬們可能還會有其他的更簡單的，或者是可以從正著想的方法，反正我不會 TAT

最后的完整代碼 QwQ

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 110;
const int M = N * N;
const int K = 30;

int n, m, C, T;
int dist[N][N][K];
int tmp1[N], tmp2[N];
int p[N], c[N];
int f[N][M];
int g[N][N];

signed main()
{
    cin >> n >> m >> C >> T;
    for(int i = 1 ; i <= n ; i ++ ) cin >> p[i] >> c[i];
    for(int i = 1 ; i <= n ; i ++ ) c[i] = min(C, c[i]);
    for(int u = 0 ; u <= 18 ; u ++ )
        for(int i = 1 ; i <= n ; i ++ )
            for(int j = 1 ; j <= n ; j ++ )
                dist[i][j][u] = -1e18;
    for(int i = 1 ; i <= n ; i ++ ) dist[i][i][0] = 0;
    for(int i = 1 ; i <= m ; i ++ )
    {
        int a, b, l;
        cin >> a >> b >> l;
        dist[a][b][0] = max(dist[a][b][0], l);
    }
    for(int u = 1 ; u <= 18 ; u ++ )
        for(int k = 1 ; k <= n ; k ++ )
            for(int i = 1 ; i <= n ; i ++ )
                for(int j = 1 ; j <= n ; j ++ )
                    dist[i][j][u] = max(dist[i][k][u - 1] + dist[k][j][u - 1], dist[i][j][u]);
    
    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j] = -1e18;
        tmp2[i] = 0;
        for(int u = 18 ; u >= 0 ; u -- )
            if(c[i] & (1 << u))
            {
                for(int j = 1 ; j <= n ; j ++ )
                    for(int k = 1 ; k <= n ; k ++ )
                    tmp1[j] = max(tmp1[j], tmp2[k] + dist[k][j][u]);
                for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j];
            }
        for(int j = 1 ; j <= n ; j ++ ) g[i][j] = tmp2[j];
    }
    
    for(int cost = 0 ; cost <= n * n ; cost ++ )
        for(int i = 1 ; i <= n ; i ++ )
            if(p[i] <= cost)
                for(int j = 1 ; j <= n ; j ++ )
                    f[i][cost] = max(f[i][cost], f[j][cost - p[i]] + g[i][j]);
    while(T -- )
    {
        int s, q, d;
        cin >> s >> q >> d;
        bool st = false;
        for(int i = 0 ; i <= q + 1 ; i ++ )
            if(f[s][i] >= d)
            {
                cout << q - i << endl;
                st = true;
                break;
            }
        if(st == false) cout << "-1\n";
    }
    return 0;
}