考试的时候是这么想的：
求出每一个点花掉 $i$ 的花费向其他点尽可能走的最长距离，然后二分这个花费，找到第一个大于 $d$ 的就输出$.$
然而，我这个记忆化搜索 $TLE$ 的很惨$.$
这里讲一下正解：
上面的大题思路是正确的，但是记忆化搜索太慢，考虑倍增 $floyd.$
令 $f[i][j]$ 表示 $i$ 号点花费 $j$ 能走的最远距离$.$
令 $go[i][j][k]$ 表示 $i$ 号点走到 $j$ 号点走 $k$ 步的最远距离(在 $i$ 号点加一次油)$.$
如果能求出 $g[i][j]$,那么 $f[i][j]$ 就表示成 $max(f[i][j],g[i][k][c[i]]+f[k][j-p[i]]).$
考虑如何求 $g[i][j][k]$:
令 $dis[i][j][k]$ 表示 $i$ 到 $j$ 走 $2^{k}$ 步的最远距离$.$
则 $go[i][j][k]=max(go[i][j][k],go[i][a][k-2^l]+dis[i][j][2^{k}])$
将 $c[i]$ 按照二进制展开，那么可以从低到高位枚举这个 $2^l$，将$go[i][j][k]$ 中第三维压掉，直接是 $tmp[i][j]=max(tmp[i][j],go[i][k]+dis[k][j][l])$ $.$ 反正这 $c[i]$ 步都要走完，直接枚举二进制就好了.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 103
#define inf 1000000300
#define setIO(s) freopen(s".in","r",stdin) //, freopen(s".out","w",stdout)
using namespace std;
int n,m,C,T;
int p[N],c[N],dis[N][N][22],go[N][N],tmp[N][N],f[N][N*N];
int main()
{
int i,j,k;
// setIO("input");
scanf("%d%d%d%d",&n,&m,&C,&T);
memset(dis,0xc2,sizeof dis);
for(i=1;i<=n;++i) scanf("%d%d",&p[i],&c[i]), dis[i][i][0]=0;
for(i=1;i<=m;++i)
{
int a,b,l;
scanf("%d%d%d",&a,&b,&l);
dis[a][b][0]=max(dis[a][b][0], l);
}
for(int t=1;t<=20;++t)
{
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
dis[i][j][t]=max(dis[i][j][t], dis[i][k][t-1]+dis[k][j][t-1]);
}
for(i=1;i<=n;++i)
{
int cc=min(c[i], C);
for(j=1;j<=n;++j) go[i][j]=tmp[i][j]=-inf;
go[i][i]=0;
for(int l=0;l<=20;++l)
{
if((1<<l)&cc)
{
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
tmp[i][j]=max(tmp[i][j], go[i][k]+dis[k][j][l]);
for(j=1;j<=n;++j) go[i][j]=tmp[i][j];
}
}
}
for(i=1;i<=n;++i) f[i][0]=0;
for(j=1;j<=n*n;++j)
{
for(i=1;i<=n;++i)
if(j>=p[i])
{
for(k=1;k<=n;++k)
f[i][j]=max(f[i][j], go[i][k]+f[k][j-p[i]]);
}
}
int cas;
for(cas=1;cas<=T;++cas)
{
int s,q,d;
scanf("%d%d%d",&s,&q,&d);
int l=1,r=q,mid,ans=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(f[s][mid]>=d) ans=mid,r=mid-1;
else l=mid+1;
}
// printf("%d
",f[s][ans]);
printf("%d
",ans==-1?ans:q-ans);
}
return 0;
}