题目简述
在一幅有向图（$n \le 100,m \le 1000$）上，你有一辆油量上限为 $C$ 的车，当油量为正整数时你可以花费$1$的油从任意一个点走到它指向的一个点，此时经过了 $l_i$ 的路程。在第$i$个点上有两个数据$p_i,c_i$，表示你可以在第 $i$ 个点上当自己的油量小于 $c_i$ 时花费 $p_i$ ($1\le p_i,c_i\le 10^5$)的钱把自己的油量设置成 $min\{c_i,C\}$。
现在有 $T$ 组询问，第 $i$ 组询问给出你的起点 $s_i$，你出发时带的预算 $q_i$ 和你希望走的路程 $d_i$。对于每次询问，输出最多能剩的钱。若无法走够 $d_i$ 的路程，输出-1（$1\le q_i\le n^2$，$1\le d_i\le 10^9$）
题解
这道题太套路了。
观看数据范围，我们大抵猜到是一个多状态dp。
然后，
就有式子了。（想不到QAQ）
对于这道题，求一定路程的最少花费，能不能转化成求一定花费的最大路程呢？
我们发现，能走的路程随花费单调不减。
很好，严格单调性的函数，是可以一一映射的。如果只要求最小的，那么非严格单调性的函数，也是可以一一映射（某种意义上）的。我们求出一定花费的最大路程，然后二分花费即可。由于一条边油耗总是1，答案的正确性就有了保证。
为什么要转化成求一定花费的最大路程呢
因为
$1\le q_i\le n^2$
题中保证了 $q$ 的范围，而且和 $n$ 有关，而 $d$ 的范围大的爆炸。所以 $q$ 比 $d$ 更有可能设计到状态中，换言之，要求的是一定花费的最大路程。
并且，花钱买油跑路程，钱是决定路程的。钱还是单调的，有拓扑序，好转移；路程买点油又可以跑，显然不好转移。
我们注意到一个很重要的东西，他加油不是累加的，而是设置成一个新的值，无论之前的油有多少。
//O是加油点
O---x---x---O---x---O---x---x---x---x---x---O---...你会发现，如果我在这个地方加油了，钱数一定的话，之后的情况就是固定的了，前面的情况就没影响了。
我们喜欢固定的东西。
这也告诉我们，一次加油只决定了这次加油后到下次加油前的路程。这期间不会加油，所以钱数是不变的.
那我们就把这个东西设出来。
设 $f_{s,q}$表示在点 $s$ ，身上有 $q$ 的钱时，要在这个点加油，最多能够走的路程。
考虑转移。
如果我们当前在点 $u$ 加油，下一个要加油的地方是点 $v$ 。
有
$$ f_{u,q} = \underset{v}{\max} \{f_{v,q-p_u} + w(u,v,\max\{c_u,C\} ) \} $$
其中 $w(u,v,c)$ 表示从 $u$ 到 $v$ 中途不加油， 用 $c$ 的油能跑的最长路程。
边界很简单，$f_{i,0} = 0$ ，没钱寸步难行。
不过其实钱数小于 $p_i$ 依旧没用，必须加油，但买不起就是买不起。
由于这个式子太好求了，所以压力给到求 $w(u,v,c)$。
求 $w(u,v,c)$
首先这个 $c$ 可以直接看成边数上限。
在一个有向有权图上，怎么求固定起点终点，最总边数不超过 $c$ 的路径的长度呢？
首先大抵又是要DP的。（其他算法可以歇歇）
考虑转移。
可以怎么转移呢？
我们发现一个拓扑序，长的路径总可以被拆成更短的路径的和。于是我们可以枚举中间点 $x$（像弗洛伊德一样！）
$$ w(u,v,c) = \underset{x}{\max} \{ w(u,x,c') + w(x,v,c-c')\} $$
这本来很对的。但是尝试转移，发现复杂度不对。
但是我们敏锐的注意到，枚举 $c'$ 似乎有些多余。这条路径一定可以被分成所有可能的距离，转移一个就够了。
转移哪一个呢？
如果转移最近的，比如 $c'=1$，很不幸，你把$d$扯到复杂度里了。数变量，得到$O(n^3d)$
面对 $1 \le d \le 10^9$的数据范围，你不经陷入了沉思。
想带个 $\log$ ...
那就带呗。
你发现，我并不要所有的状态，要求的答案中每个 $u$ 只对应一个 $\max\{c_u,C\}$ ，意思是我们要精简状态数。
这道题的倍增优化有种多重背包的美。多重背包是太多重复的东西，都可以自由的选（只要个数一样就等价），于是用二进制拆分来做。
这道题，也是一样的，只要边数一样油耗就一样，我们也尝试用二进制拆分来做。
上面那个DP式子的理解方法中我们把 $u$ 和 $v$ 看成了等价的点，像区间DP一样。我们现在把它看成极性的，就是点 $u$ 往外到每个点 $v$ ，边数不超过 $c$ 的路径最长是多少。
copy 一下：
$$ w(u,v,c) = \underset{x}{\max} \{ w(u,x,c-c') + w(x,v,c')\} $$
（偷偷把 $c'$ 和 $c-c'$交换了）
我们看到，转移的前继是 $w(u,x,c-c')$ 和 $w(x,v,c')$。
- $w(u,x,c-c')$ 这一项也是点 $u$ 的状态，因为 $c-c'<c$ ，转移有拓扑序，如果正常转移，这一项一定是已知的，不用操心；
- $w(k,v,c')$ 不是点 $u$ 的状态，而且图是有向可能有环图，不存在拓扑序，所以我们不可能保证点 $v$ 的状态被转移过了。遇到这种情况，我们就要考虑预处理了。
预处理什么呢？
如果只预处理最临近的，那么预处理复杂度$O(n^3)$,后续DP复杂度$O(n^3d)$
如果预处理几乎所有的的，那么预处理复杂度$O(n^3d)$,后续DP复杂度$O(n^3)$
我们希望平衡复杂度。
倍增就是这么神奇。
倍增预处理所有边数为 $2$ 的幂的路径的答案，剩下的路径都可以由它们凑出来。
形式化的，预处理所有 $w(i,j,2^k)$的答案，记作 $g_{i,j,k}$，$k$ 为 $c$ 的最高位，即 $k = \left \lfloor \log_2{c} \right \rfloor $ ：
$$ w(u,v,c) = \underset{x}{\max} \{ w(u,x,c-2^k) + g_{x,v,k} \} $$
感性的，这样做就是将 $c$ 二进制拆分，从最低位开始，先枚举出这个距离使得答案最大的点，找到这个点后，以这个点为起点，枚举下一位的距离，直到枚举到最高位。上面的DP式子可以看做是递归形式。
那我们只需要预处理这个 $g_{i,j,k}$ 就好了。
这个转移思路和 $w$ 一模一样，只不过不用枚举路程了，其拓扑序也很明显。
$$ g_{i,j,k} = \underset{x}{\max} \{ g(i,x,k-1)+g(x,j,k-1)\} $$
边界就是 $k=0$ 时,$2^k=1$，这时候 $u$ 到 $v$ 有边就是 $1$ ，$u=v$ 则是$0$，否则访问就是非法的，设为 $-\infty$ 。
完。
复杂度分析
回顾全文，我们要求一个 $g_{i,j,k}$ ，复杂度 $O(n^3\log_2d)$ ；
要求一个 $w(u,v,c_u)$ ，复杂度 $O(n^3\log_2d)$ ；
要求一个 $f_{s,q}$ ，复杂度 $O(n^2q)$ ；
要求答案，复杂度 $O(T\log_2{q})$ ；
总时间复杂度 $T(2n^3\log_2d+n^2q+T\log_2{q})$.
带入原数据，刚刚卡着过。不过数据倒是很难卡满，速度比想的要快一点。
然后，就是代码实现啦！
AC code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,C,T;
const int N = 105;
int g[N][N][20];
int w[N][N];
int A[N],B[N];
int f[N][N*N];
int p[N],c[N];
signed main(){
cin>>n>>m>>C>>T;
for(int i=1;i<=n;i++)cin>>p[i]>>c[i],c[i]=min(c[i],C);
memset(g,-0x3f,sizeof(g));
for(int i=1,a,b,l;i<=m;i++){
cin>>a>>b>>l;
g[a][b][0] = l;
}
for(int i=1;i<=n;i++)g[i][i][0] = 0;
for(int k=1;k<20;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int x=1;x<=n;x++)
g[i][j][k] = max(g[i][j][k],g[i][x][k-1]+g[x][j][k-1]);
for(int u=1;u<=n;u++){
memset(A,-0x3f,sizeof(A));
A[u] = 0;
for(int k=0;k<20;k++){
if(!(c[u] & (1<<k)))continue;
for(int v=1;v<=n;v++){
B[v] = -0x3f3f3f3f3f3f3f3f;
for(int x=1;x<=n;x++){
B[v] = max(B[v],A[x]+g[x][v][k]);
}
}
memcpy(A,B,sizeof(B));
}
memcpy(w[u],A,sizeof(A));
}
for(int q=0;q<=n*n;q++){
for(int u=1;u<=n;u++){
if(p[u] > q)continue;
for(int v=1;v<=n;v++){
f[u][q] = max(f[v][q-p[u]]+w[u][v],f[u][q]);
}
}
}
int s,q,d;
while(T--){
cin>>s>>q>>d;
int b = lower_bound(f[s],f[s]+n*n+1,d) - f[s];
if(q<b)cout<<"-1\n";
else cout<<q-b<<'\n';
}
return 0;
}