#P17737. 逃跑线路

逃跑线路

题目描述

奶龙王国使用 Mil(秒)作为时间单位,将一天划分成 SS Mil,分别称为时刻 0,1,…,S−10,1,\ldots,S-1。

奶龙王国中有 NN 个城市和 MM 条双向道路,均从 00 开始标号。保证任两个城市之间均连通。第 ii 条道路连接城市 AiA_i 和 BiB_i,需要恰好 LiL_i Mil 通过。每天的时刻 CiC_i 后,第 ii 条道路将开始进行检查,直到当天结束。

暴暴龙组织是一个活跃在奶龙王国中的秘密团体。出于其保密性,成员不能在道路上受到检查。如果其成员想要通过道路 ii,最晚要在时刻 Ci−LiC_i-L_i 到达这条路的一端。道路的检查不会影响两端的城市。

现在有 QQ 名暴暴龙组织的成员,从 00 开始标号。第 jj 名成员在某天的时刻 TjT_j,要从城市 UjU_j 出发去城市 VjV_j。成员可以在任意城市内停留任意长的时间。注意这名成员可能会在路上花费一天以上。

请计算每名成员花费的最短时间,精确到 Mil。

输入格式

第一行四个正整数 N,M,S,QN,M,S,Q。

接下来 MM 行,第 ii 行四个正整数表示 Ai−1,Bi−1,Li−1,Ci−1A_{i-1},B_{i-1},L_{i-1},C_{i-1}。

接下来 QQ 行,第 ii 行三个正整数表示 Ui−1,Vi−1,Ti−1U_{i-1},V_{i-1},T_{i-1}。

输出格式

输出共 QQ 行,第 ii 行表示第 i−1i-1 名成员旅行所需的最短时间。

样例输入 1

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

样例输出 1

3
8
14
2
5
7

样例输入 2

6 10 100 9
5 3 4 29
1 0 6 26
0 4 2 7
0 5 18 18
2 0 79 82
3 4 35 46
1 2 15 57
2 4 3 6
4 1 21 83
3 2 47 53
0 2 63
0 4 70
0 4 98
0 5 25
0 5 19
0 4 96
0 5 2
0 3 62
0 3 83

样例输出 2

42
32
4
93
99
6
102
60
39

样例输入 3

8 12 1000000000000000 13
2 0 4451698272827 120985696255786
6 5 78520421713825 342652131468508
2 1 185377268405175 382583457603811
0 4 54350742205838 133614919589507
7 0 68486247989149 651590905094148
0 6 85177550834829 299184420663240
5 2 442329739732459 926608308293721
3 7 78020232822359 913548478810253
1 3 267796317244889 687571310475622
5 4 90590208828121 910324397566584
5 7 8414633059584 17796117322043
4 6 45682367792138 204548471584556
7 2 44779065000162
3 5 79376234836942
4 7 305556687070759
4 3 927935834343174
5 1 663284649258985
2 5 967584209777344
5 2 963749709374595
7 4 484562389171308
1 5 446160773830045
6 4 801452311055604
3 1 744524289545354
0 6 467418420721777
5 6 371181379240653

样例输出 3

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

测试点约束

对于 100%100\% 的数据,保证:

  • 2≤N≤902\le N\le 90。
  • N−1≤M≤N(N−1)2N-1\le M\le\frac{N(N-1)}2。
  • 2≤S≤10152\le S\le 10^{15}。
  • 1≤Q≤3×1061\le Q\le 3\times10^6。
  • 0≤Ai,Bi≤N−10\le A_i,B_i\le N-1。
  • Ai≠BiA_i\ne B_i。
  • 对于任意不同的 i,j∈[0,M−1]i,j\in[0,M-1],(Ai,Bi)≠(Aj,Bj)(A_i,B_i)\ne(A_j,B_j) 且 (Ai,Bi)≠(Bj,Aj)(A_i,B_i)\ne(B_j,A_j)。
  • 1≤Li≤Ci<S1\le L_i\le C_i<S。
  • 从任意城市出发走过一些边后,可以到达任意其他城市。
  • 0≤Uj,Vj≤N−10\le U_j,V_j\le N-1。
  • Uj≠VjU_j\ne V_j。
  • 0≤Tj<S0\le T_j<S。
子任务编号 限制 分值
1 N≤40, Q≤1000N\le40,\ Q\le1000 5
2 N≤40, Uj=0 (0≤j≤Q−1)N\le40,\ U_j=0\ (0\le j\le Q-1) 20
3 N≤40N\le40 10
4 N≤60N\le60 35
5 无特殊限制 30