UOJ Logo Universal Online Judge

UOJ

#613. 【JOISC2021】逃生路线

附件下载 统计

在 IOI 王国,时间的计量单位是 Byou,一天被划为 S 单位时间。每一天经过 x(0x<S) 时间后的时刻被称为时刻 x

IOI 王国有 N 座城市,编号从 0N1。城市间有 M 条双向道路,第 i(0i<M) 条道路连接城市 AiBi,并且从时刻 Ci 开始直到当天末尾这条路将进行安全检查,并且通过这条路需要 Li 单位时间。任意两个城市之间均可通过道路到达。

JOI 组织是 IOI 王国的秘密组织之一,为了保密,他们的成员不希望遇到安全检查。因此,如果 JOI 组织的成员想要通过某条路 i,他出发的时间为 x,则他到达另一端的时间为 x+Li,因此他需要保证 0xCiLi。不过安全检查并不会涉及到城市,因此即使当一条道路处于检查时期,JOI 组织的成员仍然可以停留或通过两端的城市。

JOI 组织有 Q 个成员,编号从 0Q1。第 j 个成员会从某天的时刻 j 从城市 Uj 出发,动身前往城市 Vj,他想知道他最少需要多久才能到达。在路途中,可以停留在某个城市以等待检查结束。

请你求出每个成员需要的最短时间。

输入格式

第一行四个整数 N,M,S,Q,分别表示城市数,道路数,每天时刻数,询问个数。

接下来 M 行,每行四个整数 Ai,Bi,Li,Ci 表示一条道路。

接下来 Q 行,每行三个整数 Ui,Vi,Ti 表示一次询问。

输出格式

Q 行,每行一个整数表示对于第 i 个询问,最少需要几单位时间才能到达。具体的,设出发时间为时刻 Ti,最早到达时间为 x 天后的时刻 Ti,你需要输出 xS+TiTi

样例一

input

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

output

3
8
14
2
5
7

explanation

这组数据满足 Subtask 1,3,4,5 的限制。

在时刻 5,成员 0 开始从城市 0 前往城市 3,他将花费 3 单位时间,具体的:

  1. 经过道路 1,在时刻 7 到达城市 2
  2. 经过道路 4,在时刻 8 到达城市 3

在时刻 7,成员 1 同样开始从城市 0 前往城市 3,他将花费 8 单位时间,具体的:

  1. 经过道路 0,在时刻 10 到达城市 1
  2. 经过道路 2,在时刻 14 到达城市 2
  3. 经过道路 4,在时刻 15 到达城市 3

在时刻 9,成员 2 同样开始从城市 0 前往城市 3,他将花费 14 单位时间,具体的:

  1. 在原地停留直至第二天。
  2. 经过道路 1,在时刻 2 到达城市 2
  3. 经过道路 4,在时刻 3 到达城市 3

样例二

input

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

output

42
32
4
93
99
6
102
60
39

explanation

这组数据满足所有子任务的限制。

样例三

见附件下载中的 ex_route3.inex_route3.ans

这组数据满足 Subtask 1,3,4,5 的限制。

数据范围与提示

对于所有数据,保证 2N90,N1MN(N1)2,2S1015,1Q3×106,0Ai,Bi<N,1LiCi<S,0Ui,Vi<N,UiVi,0Ti<S

对于所有数据,保证图联通,且不存在自环重边。

Subtask 1(5 points) N40,Q1000

Subtask 2(20 points) N40,Ui=0

Subtask 3(10 points) N40

Subtask 4(35 points) N60

Subtask 5(30 points) 无特殊限制。

在下发文件中,提供了一份 sample.cpp 来提供快速输入输出模板,注意如果你选择使用这份模板,你不应当使用其他包括 scanf,printf,cin,cout 在内的输入输出方式。你可以在 main 函数开始时调用 Init() 来获取输入,并在计算出答案后,保存至 ans 数组并调用 Output() 以输出答案。

时间限制:9s

空间限制:2GB