题目描述
题解
显然是跑到没油了才加油,所以设f[i,j]表示从点i开始钱为j的最大距离,逆着做
转移考虑设g[i,j,k]表示从i到j走2^k步的答案,倍增求
再求出w[i,j,k]表示从i到j走k步的答案,拆位后做log次
最后二分答案
code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define file
using namespace std;
int P[17],a[1001][3],ls[101],p[101],c[101],h,t,n,m,C,Q,i,j,k,l,r,mid,len,x,y,z,s;
ll g[101][101][17],w[101][101][17],f[10001][101],ans;
void New(int x,int y,int z) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;a[len][2]=z;}
void work1()
{
fo(l,1,16)
{
fo(i,1,n) fo(j,1,n) g[i][j][l]=g[i][j][l-1];
fo(i,1,n)
{
fo(j,1,n)
{
fo(k,1,n)
g[i][j][l]=max(g[i][j][l],g[i][k][l-1]+g[k][j][l-1]);
}
}
}
}
void work2()
{
fo(i,1,n)
{
w[i][i][0]=0;
s=min(C,c[i]);
if (s&1)
{
fo(j,1,n)
w[i][j][0]=g[i][j][0];
}
}
fo(l,1,16)
{
fo(i,1,n)
{
s=min(C,c[i]);
fo(j,1,n)
{
w[i][j][l]=w[i][j][l-1];
if (s&P[l])
{
fo(k,1,n)
w[i][j][l]=max(w[i][j][l],w[i][k][l-1]+g[k][j][l]);
}
}
}
}
}
void work3()
{
fo(i,1,n) f[0][i]=0;
fo(i,1,n*n)
{
fo(j,1,n)
{
f[i][j]=f[i-1][j];
if (i>=p[j])
{
fo(k,1,n)
f[i][j]=max(f[i][j],w[j][k][16]+f[i-p[j]][k]);
}
}
}
}
int main()
{
freopen("trip.in","r",stdin);
#ifdef file
freopen("trip.out","w",stdout);
#endif
memset(f,200,sizeof(f));
memset(g,200,sizeof(g));
memset(w,200,sizeof(w));
P[0]=1;
fo(i,1,16) P[i]=P[i-1]*2;
scanf("%d%d%d%d",&n,&m,&C,&Q);
fo(i,1,n) scanf("%d%d",&p[i],&c[i]),g[i][i][0]=0;
fo(i,1,m) scanf("%d%d%d",&j,&k,&l),New(j,k,l),g[j][k][0]=max(g[j][k][0],l);
work1();
work2();
work3();
for (;Q;--Q)
{
scanf("%d%d%d",&x,&y,&z);
l=0,r=y;
while (l<r)
{
mid=(l+r)/2;
if (f[mid][x]<z)
l=mid+1; else r=mid;
}
printf("%d\n",(f[l][x]<z)?-1:y-l);
}
fclose(stdin);
fclose(stdout);
return 0;
}