LibreOJ 539 旅游路线

首先考虑最暴力的 DP。
设 fi,c,l 表示从 i 开始，当前油量为 c，走 l 的路程最少需要多少钱。
观察数据范围可以考虑交换答案和 l 这一维。

注意到油量 c 并不那么重要。
考虑删除这一维，并钦点在 i 处加油。
转移时直接枚举下一处加油的点，并用另外一个 DP 预处理出转移值。需要倍增优化。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
const int M = 1e3;
const int MX = 1e9;
const int MXC = 1e5;
const int LG = 18;
const int Q = 1e4;
int n,m,C,T;
int p[N + 5],c[N + 5];
int to[M + 5],val[M + 5],pre[M + 5],first[N + 5];
inline void add(int u,int v,int w)
{
    static int tot = 0;
    to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int f[N + 5][Q + 5],g[N + 5][N + 5],h[LG + 5][N + 5][N + 5];
int t[2][N + 5];
inline void trans(int &x,int v)
{
    x = min(max(x,v),MX);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&C,&T);
    memset(h,-0x3f,sizeof h);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d",p + i,c + i),c[i] = min(c[i],C),h[0][i][i] = 0;
    int u,v,w;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d",&u,&v,&w),add(u,v,w),trans(h[0][u][v],w);
    for(register int l = 1;l <= LG;++l)
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= n;++j)
                for(register int k = 1;k <= n;++k)
                    trans(h[l][i][j],h[l - 1][i][k] + h[l - 1][k][j]);
    for(register int i = 1,cur;i <= n;++i)
    {
        memset(t,-0x3f,sizeof t),t[cur = 0][i] = 0;
        for(register int k = 0;k <= LG;++k)
            if(c[i] & (1 << k))
            {
                memset(t[cur ^ 1],-0x3f,sizeof t[cur ^ 1]);
                for(register int j = 1;j <= n;++j)
                    for(register int x = 1;x <= n;++x)
                        trans(t[cur ^ 1][j],t[cur][x] + h[k][x][j]);
                cur ^= 1;
            }
        memcpy(g[i],t[cur],sizeof g[i]);
    }
    for(register int q = 0;q <= Q;++q)
        for(register int i = 1;i <= n;++i)
            if(q >= p[i])
                for(register int j = 1;j <= n;++j)
                    trans(f[i][q],f[j][q - p[i]] + g[i][j]);
    for(register int i = 1;i <= n;++i)
        for(register int q = 1;q <= Q;++q)
            f[i][q] = max(f[i][q],f[i][q - 1]);
    for(int s,q,d;T;--T)
        scanf("%d%d%d",&s,&q,&d),
        printf("%d\n",max(q - (int)(lower_bound(f[s],f[s] + q + 1,d) - f[s]),-1));
}