AT_joisc2021_d.逃走経路 (Escape Route)

IOI 国的一天被划分为 $S$ 个单位时间（单位：皮秒）。每日起点开始经过 $x$ 皮秒 $(0 \leq x < S)$ 的时刻称为时刻 $x$。国家包含 $N$ 座城市（编号 $0$ 至 $N-1$）和 $M$ 条双向道路（编号 $0$ 至 $M-1$），任意两城市均可通过若干道路互通。

每条道路 $i$ $(0 \leq i \leq M-1)$ 具有以下属性：

• 连接城市 $A_i$ 与 $B_i$。
• 通行耗时 $L_i$ 皮秒。
• 每日从时刻 $C_i$ 至当日结束进行全路段检查。

JOI 团成员使用道路 $i$ 时，必须满足：

• 在时刻 $x$ 从 $A_i$ 或 $B_i$ 出发，且 $0 \leq x \leq C_i - L_i$。
• 在时刻 $x + L_i$ 到达另一城市。
  （检查期间允许停留在 $A_i$ 或 $B_i$）

现有 $Q$ 名成员（编号 $0$ 至 $Q-1$）：

• 成员 $j$ 于某日时刻 $T_j$ 从 $U_j$ 出发前往 $V_j$。
• 移动中可在城市等待（可能耗时多日）。

请计算每位成员从起点到终点的最小耗时。

---

实现细节

需实现以下函数：

#include "escape_route.h"
std::vector<long long> calculate_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
);

参数说明：

• N：城市数量。
• M：道路数量。
• S：每日总皮秒数。
• Q：成员数量。
• A, B, L, C：长度为 $M$ 的数组，描述道路 $i$（连接 $A_i$ 与 $B_i$，耗时 $L_i$，检查开始时刻 $C_i$）。
• U, V, T：长度为 $Q$ 的数组，描述成员 $j$（从 $U_j$ 于时刻 $T_j$ 出发前往 $V_j$）。

返回值：

• 长度为 $Q$ 的 long long 数组，其中 answer[j] 为成员 $j$ 的最小耗时。

本题是交互题，详见实现细节。

详见实现细节。

样例解释

• 成员 $0$（耗时 $3$ 皮秒）：
  • 时刻 $5$：城市 $0$ → 道路 $1$（耗时 $2$）→ 城市 $2$（时刻 $7$）。
  • 时刻 $7$：城市 $2$ → 道路 $4$（耗时 $1$）→ 城市 $3$（时刻 $8$）。
• 成员 $2$（耗时 $14$ 皮秒）：
  • 在城市 $0$ 等待至次日时刻 $0$。
  • 时刻 $0$：城市 $0$ → 道路 $1$（耗时 $2$）→ 城市 $2$（时刻 $2$）。
  • 时刻 $2$：城市 $2$ → 道路 $4$（耗时 $1$）→ 城市 $3$（时刻 $3$）。

数据范围

• $2 \leq N \leq 90$
• $N(N-1) \leq M \leq \dfrac{N(N-1)}{2}$
• $2 \leq S \leq 10^{15}$
• $1 \leq Q \leq 3 \times 10^{6}$
• $0 \leq A_i, B_i, U_j, V_j \leq N-1$
• $A_i \neq B_i$，$U_j \neq V_j$
• $1 \leq L_i < S$，$L_i \leq C_i < S$
• $0 \leq T_j < S$
• 图连通

子任务

1. ($5$ 分) $N \leq 40$，$Q \leq 1000$
2. ($20$ 分) $N \leq 40$，所有 $U_j = 0$
3. ($10$ 分) $N \leq 40$
4. ($35$ 分) $N \leq 60$
5. ($30$ 分) 无特殊限制

本翻译由 Deepseek R1 大模型生成。