#539. 「LibreOJ NOIP Round #1」旅游路线

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: spj

题目描述

T 城是一个旅游城市,具有 nn 个景点和 mm 条道路,所有景点编号为 1,2,...,n1,2,...,n。每条道路连接这 nn 个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。

为了方便旅游,每个景点都有一个加油站。第 ii 个景点的加油站的费用为 pip_i,加油量为 cic_i。若汽车在第 ii 个景点加油,则需要花费 pip_i 元钱,之后车的油量将被加至油量上限与 cic_i 中的较小值。不过如果加油前汽车油量已经不小于 cic_i,则不能在该景点加油。

小 C 准备来到 T 城旅游。他的汽车油量上限为 CC。旅游开始时,汽车的油量为 00。在旅游过程中:

1、当汽车油量大于 00 时,汽车可以沿从当前景区出发的任意一条道路到达另一个景点(不能只走道路的一部分),汽车油量将减少 11

2、当汽车在景点 ii 且当前油量小于 cic_i 时,汽车可以在当前景点加油,加油需花费 pip_i 元钱,这样汽车油量将变为 min{ci,C}\min\{c_i,C\}

一次旅游的总花费等于每次加油的花费之和,旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油,费用也要计算多次,同样地,多次经过同一条道路,路程也要计算多次。

小 C 计划旅游 TT 次,每次旅游前,小 C 都指定了该次旅游的起点和目标路程。由于行程不同,每次出发前带的钱也不同。为了省钱,小 C 需要在旅游前先规划好旅游路线(包括旅游的路径和加油的方案),使得从起点出发,按照该旅游路线旅游结束后总路程不小于目标路程,且剩下的钱尽可能多。请你规划最优旅游路线,计算这 TT 次旅游每次结束后最多可以剩下多少钱。

输入格式

输入第一行包含四个正整数 nnmmCCTT,每两个整数之间用一个空格隔开,分别表示景点数、道路数、汽车油量上限和旅行次数。

接下来 nn 行,每行包含两个正整数 pip_icic_i,每两个整数之间用一个空格隔开,按编号顺序依次表示编号为 1,2,...,n1,2,...,n 的景点的费用和油量。

接下来 mm 行,每行包含三个正整数 aia_ibib_ilil_i,每两个整数之间用一个空格隔开,表示一条从编号为 aia_i 的景点到编号为 bib_i 的景点的道路,道路的长度为 lil_i。保证 aibia_i\ne b_i,但从一个景点到另一个景点可能有多条道路。

最后 TT 行,每行包含三个正整数 sis_iqiq_idid_i,描述一次旅游计划,旅游的起点为编号为 sis_i 的景点,出发时带了 qiq_i 元钱,目标路程为 did_i

输出格式

输出 TT 行,每行一个整数,第 ii 行的整数表示第 ii 次旅游结束后最多剩下多少元钱。如果旅游无法完成,也就是说不存在从景点 sis_i 出发用不超过 qiq_i 元钱经过不小于 did_i 的路程的路线,则该行输出 1-1

样例

样例输入 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

样例输出 1

2
-1

样例解释

T 城的景区和道路如下图所示:

由图可知,从景点 11 出发,路程为 33 的路线有两条:12461\rightarrow 2\rightarrow 4\rightarrow 613561\rightarrow 3\rightarrow 5\rightarrow 6

11 次旅游,最优路线为先在景点 11 加油,花费 44 元,此时油量为 11,然后到景点 22,此时油量为 00,在景点 22 加油,花费 66 元,此时油量为 22,接着到景点 44,此时油量为 11,最后到景点 66,总路程为 33,最后剩余 1246=212-4-6=2 元。

22 次旅游,只用 99 元无论如何也无法走 33 的路程,因此旅游无法完成。

样例 2

见附加文件(在页面上方下载)中的选手目录下的 trip2.intrip2.ans

数据范围与提示

所有测试数据的范围和特点如下表所示:

测试点编号nnmmCCTTpi, cip_i, \ c_i特殊性质
110\le 10=n1=n-110\le 10=1=110\le 101, 2
210\le 10
3
4
5=10=10=10=102
6=15=15=15=1520\le 20
7=20=20=20=20
8100\le 100=n1=n-1103\le 10^350\le 50100\le 1001, 3
9
10
1140\le 40400\le 4003
12
1360\le 60600\le 600103\le 10^3
14
1580\le 80800\le 800
16105\le 10^5103\le 10^3105\le 10^5
1790\le 90900\le 900
18
19100\le 1001000\le 1000
20105\le 10^5

其中,“特殊性质”一列中的数字意义如下:

  • 特殊性质 1:所有 ai=ia_i=ibi=i+1b_i=i+1li=1l_i=1

  • 特殊性质 2:所有 di103d_i\le 10^3

  • 特殊性质 3:所有 qi100q_i\le 100

对于所有数据,2n1002\le n\le 1001m10001\le m\le 10001C,T1051\le C,T\le 10^51ai,bi,lin1\le a_i,b_i,l_i\le n1pi,ci1051\le p_i,c_i\le 10^51sin1\le s_i\le n1qin21\le q_i\le n^21di1091\le d_i\le 10^9