这道题虽然没切，但还是决定写一下总结。
因为这道题的加油是直接赋值，所以可以考虑每次枚举下一个加油的点。
设f[i][j]表示当前到第i个点，剩余钱数为j，走的最大路程，因为路程是随钱数单调递增的，所以可以二分。
再设一个辅助转移的数组，g[i][j][k]表示从i点走到j点，花费不超过2^k步时所能走的最大路程。
然后就有转移：f[x][j]=max(f[y][j-p[x]]+dis[x][y])
现在切了题，发现总结没讲完全，回来补一下。
如果转移的时候需要注意一下细节，比如g,dis的初始值都应该赋值成-1e9，因为如果不赋初值会导致两个本来不能到达的点发生转移。
还有就是要注意不能重复转移。
#include<cstdio> #include<cstring> #include<algorithm> #define N 110 #define M 1010 #define K 20 #pragma GCC optimize(2) using namespace std; int n,m,C,T,i,j,k,p[N],c[N],x,y,l,q[N],f[N][N*N],dis[N][N],g[N][N][K],data[N*N*N*2][3],bz[N*N],temp[N][N],st,Q,d; int find(int x,int k){ int ans=1e9,l=0,r=n*n,mid; while (l<=r){ mid=(l+r)/2; if (f[x][mid]>=k){ ans=mid; r=mid-1; } else l=mid+1; } return ans; } int main(){ freopen("trip.in","r",stdin); freopen("trip.out","w",stdout); scanf("%d%d%d%d",&n,&m,&C,&T); for (i=1;i<=n;i++) scanf("%d%d",&p[i],&c[i]),c[i]=min(c[i],C); for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (l=0;l<K;l++) g[i][j][l]=-1e9; for (i=1;i<=n;i++) for (j=1;j<=n;j++) dis[i][j]=-1e9; for (i=1;i<=n;i++) for (j=1;j<=n;j++) temp[i][j]=-1e9; for (i=1;i<=n;i++) g[i][i][0]=0,dis[i][i]=0; for (i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&l); g[x][y][0]=max(l,g[x][y][0]); } for (l=1;l<K;l++) for (i=1;i<=n;i++) for (j=1;j<=n;j++){ g[i][j][l]=g[i][j][l-1]; for (k=1;k<=n;k++) g[i][j][l]=max(g[i][k][l-1]+g[k][j][l-1],g[i][j][l]); } for (l=0;l<K;l++){ for (i=1;i<=n;i++) if (c[i]&(1<<l)) for (j=1;j<=n;j++) for (k=1;k<=n;k++) temp[i][j]=max(temp[i][j],dis[i][k]+g[k][j][l]); for (i=1;i<=n;i++) for (j=1;j<=n;j++) dis[i][j]=max(dis[i][j],temp[i][j]); } for (l=1;l<=n*n;l++){ for (i=1;i<=n;i++) if (l>=p[i]) for (j=1;j<=n;j++) f[i][l]=max(f[i][l],f[j][l-p[i]]+dis[i][j]); } while (T--){ scanf("%d%d%d",&st,&Q,&d); Q-=find(st,d); printf("%d ",max(Q,-1)); } return 0; }