AT_joisc2021_d 逃走経路 (Escape Route)

秘密组织 JOI 团在 IOI 国活动，成员需避开道路检查点完成城市间移动。

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$。 - 移动中可在城市等待（可能耗时多日）。 请计算每位成员从起点到终点的最小耗时。 ---------------- #### 实现细节 需实现以下函数： ```cpp #include "escape_route.h" std::vector calculate_necessary_time( int N, int M, long long S, int Q, std::vector A, std::vector B, std::vector L, std::vector C, std::vector U, std::vector V, std::vector 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 大模型生成。