3991: 「LibreOJ NOIP Round #1」旅游路线
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
T 城是一个旅游城市，具有 $n$ 个景点和 $m$ 条道路，所有景点编号为 $1,2,...,n$。每条道路连接这 $n$ 个景区中的某两个景区，道路是**单向通行**的。每条道路都有一个长度。
为了方便旅游，每个景点都有一个加油站。第 $i$ 个景点的加油站的费用为 $p_i$，加油量为 $c_i$。若汽车在第 $i$ 个景点加油，则需要花费 $p_i$ 元钱，之后车的油量将**被加至**油量上限与 $c_i$ 中的较小值。不过如果加油前汽车油量已经不小于 $c_i$，则不能在该景点加油。
小 C 准备来到 T 城旅游。他的汽车油量上限为 $C$。旅游开始时，汽车的油量为 $0$。在旅游过程中：
1、当汽车油量大于 $0$ 时，汽车可以沿从当前景区出发的任意一条道路**到达**另一个景点（不能只走道路的一部分），汽车油量将减少 $1$；
2、当汽车在景点 $i$ 且当前油量小于 $c_i$ 时，汽车可以在当前景点加油，加油需花费 $p_i$ 元钱，这样汽车油量将变为 $\min\{c_i,C\}$。
一次旅游的总花费等于每次加油的花费之和，旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油，费用也要计算多次，同样地，多次经过同一条道路，路程也要计算多次。
小 C 计划旅游 $T$ 次，每次旅游前，小 C 都指定了该次旅游的起点和目标路程。由于行程不同，每次出发前带的钱也不同。为了省钱，小 C 需要在旅游前先规划好旅游路线（包括旅游的路径和加油的方案），使得从起点出发，按照该旅游路线旅游结束后总路程不小于目标路程，且剩下的钱尽可能多。请你规划最优旅游路线，计算这 $T$ 次旅游每次结束后最多可以剩下多少钱。
输入
输入第一行包含四个正整数 $n$，$m$，$C$，$T$，每两个整数之间用一个空格隔开，分别表示景点数、道路数、汽车油量上限和旅行次数。
接下来 $n$ 行，每行包含两个正整数 $p_i$，$c_i$，每两个整数之间用一个空格隔开，按编号顺序依次表示编号为 $1,2,...,n$ 的景点的费用和油量。
接下来 $m$ 行，每行包含三个正整数 $a_i$，$b_i$，$l_i$，每两个整数之间用一个空格隔开，表示一条从编号为 $a_i$ 的景点到编号为 $b_i$ 的景点的道路，道路的长度为 $l_i$。保证 $a_i\ne b_i$，但从一个景点到另一个景点可能有多条道路。
最后 $T$ 行，每行包含三个正整数 $s_i$，$q_i$，$d_i$，描述一次旅游计划，旅游的起点为编号为 $s_i$ 的景点，出发时带了 $q_i$ 元钱，目标路程为 $d_i$。
输出
输出 $T$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次旅游结束后最多剩下多少元钱。如果旅游无法完成，也就是说不存在从景点 $s_i$ 出发用不超过 $q_i$ 元钱经过不小于 $d_i$ 的路程的路线，则该行输出 $-1$。
样例输入 复制
6 6 3 2
4 1
6 2
2 1
8 1
5 4
9 1
1 2 1
1 3 1
2 4 1
3 5 1
4 6 1
5 6 1
1 12 3
1 9 3样例输出 复制
2
-1提示
数据范围：所有测试数据的范围和特点如下表所示： | 测试点编号 | $n$ | $m$ | $C$ | $T$ | $p_i, \ c_i$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | 1 | $\le 10$ | $=n-1$ | $\le 10$ | $=1$ | $\le 10$ | 1, 2 | | 2 | $\le 10$ | $=n-1$ | $\le 10$ | $\le 10$ | $\le 10$ | 1, 2 | | 3 | $\le 10$ | $=n-1$ | $\le 10$ | $\le 10$ | $\le 10$ | 1, 2 | | 4 | $\le 10$ | $=n-1$ | $\le 10$ | $\le 10$ | $\le 10$ | 1, 2 | | 5 | $=10$ | $=10$ | $\le 10$ | $\le 10$ | $\le 10$ | 2 | | 6 | $=15$ | $=15$ | $\le 10$ | $\le 20$ | $\le 10$ | 2 | | 7 | $=20$ | $=20$ | $\le 10$ | $\le 20$ | $\le 10$ | 2 | | 8 | $\le 100$ | $=n-1$ | $\le 10^3$ | $\le 50$ | $\le 100$ | 1, 3 | | 9 | $\le 100$ | $=n-1$ | $\le 10^3$ | $\le 50$ | $\le 100$ | 1, 3 | | 10 | $\le 100$ | $=n-1$ | $\le 10^3$ | $\le 50$ | $\le 100$ | 1, 3 | | 11 | $\le 40$ | $\le 400$ | $\le 10^3$ | $\le 50$ | $\le 100$ | 3 | | 12 | $\le 40$ | $\le 400$ | $\le 10^3$ | $\le 50$ | $\le 100$ | 3 | | 13 | $\le 60$ | $\le 600$ | $\le 10^3$ | $\le 50$ | $\le 10^3$ | 无 | | 14 | $\le 60$ | $\le 600$ | $\le 10^3$ | $\le 50$ | $\le 10^3$ | 无 | | 15 | $\le 80$ | $\le 800$ | $\le 10^3$ | $\le 50$ | $\le 10^3$ | 无 | | 16 | $\le 80$ | $\le 800$ | $\le 10^5$ | $\le 10^3$ | $\le 10^5$ | 无 | | 17 | $\le 90$ | $\le 900$ | $\le 10^5$ | $\le 10^3$ | $\le 10^5$ | 无 | | 18 | $\le 90$ | $\le 900$ | $\le 10^5$ | $\le 10^3$ | $\le 10^5$ | 无 | | 19 | $\le 100$ | $\le 1000$ | $\le 10^5$ | $\le 10^3$ | $\le 10^5$ | 无 | | 20 | $\le 100$ | $\le 1000$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 无 | 其中，“特殊性质”一列中的数字意义如下： * 特殊性质 1：所有 $a_i=i$，$b_i=i+1$，$l_i=1$。 * 特殊性质 2：所有 $d_i\le 10^3$。 * 特殊性质 3：所有 $q_i\le 100$。 对于所有数据，$2\le n\le 100$，$1\le m\le 1000$，$1\le C,T\le 10^5$，$1\le a_i,b_i,l_i\le n$，$1\le p_i,c_i\le 10^5$，$1\le s_i\le n$，$1\le q_i\le n^2$，$1\le d_i\le 10^9$。