首先考虑最暴力的 DP。
设 \(f_{i,c,l}\) 表示从 \(i\) 开始，当前油量为 \(c\)，走 \(l\) 的路程最少需要多少钱。
观察数据范围可以考虑交换答案和 \(l\) 这一维。
注意到油量 \(c\) 并不那么重要。
考虑删除这一维，并钦点在 \(i\) 处加油。
转移时直接枚举下一处加油的点，并用另外一个 DP 预处理出转移值。需要倍增优化。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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));
}