题目描述

题目译自 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}。

• $\texttt{std::vector caculate_necessary_time(}$
  $\texttt{ int N, int M, long long S, int Q, std::vector A, std::vectorB,}$
  $\texttt{ std::vector L, std::vector C, std::vector U,}$
  $\texttt{ std::vector V, std::vector 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。
  </li> </ul>

  编译及测试

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

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

  $$\texttt{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$	-

  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$。

  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
  

  这组样例满足所有子任务的限制。

  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$ 的限制。