题目描述

题目译自 JOISC 2021 Day2 T1「逃走経路 / Escape Route」

在 IOI 王国，人们使用 Byou 作为时间单位。IOI 王国中的一天被分为了 $S$ 个时间单位。每天从最开始经过 $x$ $(0 \le x < S)$ Byou 后的时间称为时刻 $x$。

IOI 王国由 $N$ 个城市组成，以 $0$ 到 $N-1$ 编号。其中有 $M$ 条双向道路连接某些城市，以 $0$ 到 $M-1$ 编号。你可以通过这些道路从一个城市到达另一个城市。第 $i$ $(0 \le i \le M-1)$ 条道路连接城市 $A_i$ 和 $B_i$，且经过这条道路需要 $L_i$ Byou。

在每天，人们会在道路 $i$ 进行一次严格的安检，并从时刻 $C_i$ 持续到当天结束。

JOI 帮是 IOI 王国的一个秘密组织。由于其神秘性，JOI 帮的成员构成是高度机密。这意味着其中的成员不能遭遇任何一次安检。因此，如果 JOI 帮的成员需要经过道路 $i$，TA 从 $A_i$ 或 $B_i$ 起身出发的时刻 $x$ 必须满足 $0 \le x \le C_i - L_i$。由于安检并非在城市内进行，而是在路上，所以 JOI 帮的成员可以在道路 $i$ 安检时出现在城市 $A_i$ 或 $B_i$。

JOI 帮有 $Q$ 个成员，以 $0$ 到 $Q-1$ 编号。成员 $j$ $(0 \le j \le Q-1)$ 会在某天的时刻 $T_j$ 从城市 $U_j$ 出发前往城市 $V_j$。成员们可以在途中的某个城市里小憩一会。成员 $j$ 可能需要很多天才能到达城市 $V_j$。

请您编写一个程序，对于给定的城市、道路、安检和 JOI 帮的成员的信息，对于每个 $j$ $(0 \le j \le Q-1)$ 计算出成员 $j$ 从 $U_j$ 到达 $V_j$ 的最少时间。

实现细节

为了减少输入和输出的时间，这道题目由计分器计分。

您需要提交一份文件。它的文件名为 $\texttt{escape\_route.cpp}$。其中需要实现以下函数。您的程序必须通过预处理指令 $\texttt{\#include}$ 包含 $\texttt{escape\_route.h}$。

std::vector<long long> caculate_necessary_time(
    int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
    std::vector<int> V, std::vector<long long> T)

这个函数将被每组测试数据调用恰好一次。

• 参数 $\texttt{N}$ 是 IOI 王国中城市的个数。
• 参数 $\texttt{M}$ 是 IOI 王国中道路的个数。
• 参数 $\texttt{S}$ 表示 IOI 王国的一天被划分为 $S$ Byou。
• 参数 $\texttt{Q}$ 是 JOI 帮的成员个数。
• 参数 $\texttt{A, B, L, C}$ 是长度为 $M$ 的数组。它们表示道路 $i$ $(0 \le i \le M-1)$ 连接城市 $\texttt{A[i]}$ 和城市 $\texttt{B[i]}$，需要花费 $\texttt{L[i]}$ Byou 通过，且每天会从时刻 $\texttt{C[i]}$ 开始安检。
• 参数 $\texttt{U, V, T}$ 是长度为 $Q$ 的数组。它们表示成员 $j$ $(0 \le j \le Q-1)$ 在时刻 $\texttt{T[j]}$ 从城市 $\texttt{U[j]}$ 出发前往城市 $\texttt{V[j]}$。

这个函数应当返回一个长度为 $Q$ 的，$\texttt{long long}$ 类型的数组 $\texttt{answer}$。它表示，对于每个 $0 \le j \le Q-1$，成员 $j$ 从城市 $\texttt{U[j]}$ 到达城市 $\texttt{V[j]}$ 的最小时间为 $\texttt{answer[j]}$ Byou。

编译及测试

您可以从附加文件中下载一个压缩文件，它包含了您用以测试程序的计分器。这个压缩文件中也包含了一份样例程序。

评分器是文件 $\texttt{grader.cpp}$。为了测试您的程序，请把 $\texttt{grader.cpp, escape\_route.cpp, escape\_route.h}$ 放在同一目录中，并执行以下指令以编译您的程序。

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp

待编译成功，您就生成了一个可执行文件 $\texttt{grader}$。

在这道题中，附加文件中提供的计分器是与最后评测时使用的计分器一致的。

输入格式

第一行，四个整数 $N$, $M$, $S$, $Q$。 以下 $M$ 行，每行 $4$ 个整数 $A_i$, $B_i$, $L_i$, $C_i$。 以下 $Q$ 行，每行 $3$ 个整数 $U_j$, $V_j$, $T_j$。

输出格式

计分器输出 $Q$ 行到标准输出。第 $k+1$ $(0 \le k \le Q-1)$ 行包含 $\texttt{answer[k]}$。

数据范围

对于所有的数据，满足：

• $2 \le N \le 90$
• $N-1 \le M \le \frac{N(N-1)}{2}$
• $2 \le S \le 1\,000\,000\,000\,000\,000 = 10^{15}$
• $1 \le Q \le 3\,000\,000$
• $0 \le A_i \le N-1$ $(0 \le i \le M-1)$
• $0 \le B_i \le N-1$ $(0 \le i \le M-1)$
• $A_i \ne B_i$ $(0 \le i \le M-1)$
• $(A_i,B_i) \ne (A_k,B_k),(A_i,B_i) \ne (B_k,A_k)$ $(0 \le i < k \le M-1)$
• $1 \le L_i < S$ $(0 \le i \le M-1)$
• $L_i \le C_i < S$ $(0 \le i \le M-1)$
• 您可以通过城市之间的某些道路从任意城市到达任意其他城市
• $0 \le U_j \le N-1$ $(0 \le j \le Q-1)$
• $0 \le V_j \le N-1$ $(0 \le j \le Q-1)$
• $U_j \ne V_j$ $(0 \le j \le Q-1)$
• $0 \le T_j < S$ $(0 \le j \le Q-1)$

各子任务及其限制见下表：

子任务编号	分值	限制
1	$5$	$N \le 40$，$Q \le 1\,000$
2	$20$	$N \le 40$，$U_j = 0$ $(0 \le j \le Q-1)$
3	$10$	$N \le 40$
4	$35$	$N \le 60$
5	$30$	-

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

输出

3
8
14
2
5
7

这组样例满足子任务 $1,3,4,5$ 的限制。

在时刻 $5$，成员 $0$ 从城市 $0$ 出发前往城市 $3$。如果成员 $0$ 按如下方法行进，需要 $3$ Byou：

• 在时刻 $5$ 从城市 $0$ 出发，经过道路 $1$ 在时刻 $7$ 到达城市 $2$。
• 在时刻 $7$ 从城市 $2$ 出发，经过道路 $4$ 在时刻 $8$ 到达城市 $3$。

由于这是最小值，所以 $\texttt{answer[0]}=3$。

在时刻 $7$，成员 $1$ 从城市 $0$ 出发前往城市 $3$。如果成员 $1$ 按如下方法行进，需要 $8$ Byou：

• 在时刻 $7$ 从城市 $0$ 出发，经过道路 $0$ 在时刻 $10$ 到达城市 $1$。
• 在时刻 $10$ 从城市 $1$ 出发，经过道路 $2$ 在时刻 $14$ 到达城市 $2$。
• 在时刻 $14$ 从城市 $2$ 出发，经过道路 $4$ 在时刻 $15$ 到达城市 $3$。

由于这是最小值，所以 $\texttt{answer[1]}=8$。

在时刻 $9$，成员 $2$ 从城市 $0$ 出发前往城市 $3$。如果成员 $1$ 按如下方法行进，TA 会在次日抵达城市 $3$，总共需要 $14$ Byou：

• 在城市 $0$ 摸鱼直到次日的时刻 $0$。
• 在时刻 $0$ 从城市 $0$ 出发，经过道路 $1$ 在时刻 $2$ 到达城市 $2$。
• 在时刻 $2$ 从城市 $2$ 出发，经过道路 $4$ 在时刻 $3$ 到达城市 $3$。

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

输出

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

输出

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

这组样例满足子任务 $1,3,4,5$ 的限制。