P14376 [JOISC 2018] 野猪 / Wild Boar

JOI-kun 是一只生活在 IOI 森林中的野猪，森林中有 $N$ 个补给站和 $M$ 条道路。补给站编号为 $1$ 至 $N$。第 $i$ 条道路（$1 \le i \le M$）双向连接补给站 $A_i$ 和 $B_i$，JOI-kun 沿该道路往返任一方向均需耗时 $C_i$ 小时。从任意补给站出发，均可经由一条或多条道路抵达其他任意补给站。 JOI-kun 不擅长掉头。他不能在道路中途掉头返回刚离开的补给站。此外，当他通过某条道路抵达一个补给站后，不能沿原路立即返回上一个补给站。 每天，JOI-kun 根据 **补给计划** 在补给站供应食物。每日的补给计划由一个长度为 $L$ 的补给站序列 $X_1, X_2, \ldots, X_L$ 组成。他从补给站 $X_1$ 开始供应，按顺序访问各补给站，最终在补给站 $X_L$ 结束供应。途中允许经过其他补给站。他可能多次在同一个补给站供应食物，但需满足对每个 $j$（$1 \le j \le L - 1$），有 $X_j \ne X_{j+1}$。请注意，可能存在他无法执行的补给计划。 初始时，JOI-kun 制定初始补给计划 $X_1, X_2, \ldots, X_L$。在第 $k$ 天早晨（$1 \le k \le T$），他会将计划中第 $P_k$ 个值修改为 $Q_k$（即 $X_{P_k}$ 变为 $Q_k$），然后按新计划供应食物。修改后，对每个 $j$（$1 \le j \le L - 1$），仍满足 $X_j \ne X_{j+1}$。 对于 $T$ 天内每一天的补给计划，JOI-kun 希望判断他是否能够执行该计划；若可以执行，则求出按该计划供应食物所需的最短时间。 **任务** 给定 IOI 森林的数据和 JOI-kun 的补给计划，对于 $T$ 天内每一天的补给计划，编写一个程序，判断他是否能够执行该计划；若可以执行，则求出按该计划供应食物所需的最短时间。

从标准输入读取以下数据： - 输入第一行包含四个以空格分隔的整数 $N$、$M$、$T$ 和 $L$。这表示 IOI 森林中有 $N$ 个补给站和 $M$ 条道路，JOI-kun 考虑 $T$ 天的补给计划，且补给计划由长度为 $L$ 的序列构成。 - 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含三个以空格分隔的整数 $A_i$、$B_i$ 和 $C_i$。这表示第 $i$ 条道路双向连接补给站 $A_i$ 和 $B_i$，JOI-kun 沿该道路往返任一方向均需耗时 $C_i$ 小时。 - 接下来的 $L$ 行中，第 $j$ 行（$1 \le j \le L$）包含一个整数 $X_j$。这表示初始补给计划为 $X_1, X_2, \ldots, X_L$。 - 接下来的 $T$ 行中，第 $k$ 行（$1 \le k \le T$）包含两个以空格分隔的整数 $P_k$ 和 $Q_k$。这表示 JOI-kun 将在第 $k$ 天早晨把补给计划中的第 $P_k$ 个值修改为 $Q_k$。

向标准输出写入 $T$ 行。第 $k$ 行（$1 \le k \le T$）应包含 $-1$，若他在第 $k$ 天无法执行补给计划；否则，输出他能够执行该计划所需的最短时间（单位：小时）。

### 样例 1 解释 在样例输入 1 中，初始补给计划为 1、2、3。JOI-kun 在第 1 天早晨将该补给计划的第 3 个值修改为 1。因此，第 1 天的补给计划为 1、2、1。 首先，JOI-kun 在补给站 1 供应食物。接着，他使用第 1 条道路从补给站 1 前往补给站 2，并在补给站 2 供应食物。然后，他使用第 2 条道路从补给站 2 前往补给站 3。最后，他使用第 3 条道路从补给站 3 前往补给站 1，并在补给站 1 供应食物。如此执行补给计划共需 3 小时。由于这是可能的最短时间，输出 3。 请注意，JOI-kun 不能按 1 → 2 → 1 的路径移动，因为他不能掉头。 ### 样例 2 解释 在样例输入 2 中，第 1 天的补给计划为 4、1、4。首先，JOI-kun 在补给站 4 供应食物。接着，他使用第 4 条道路从补给站 4 前往补给站 1，并在补给站 1 供应食物。然后，他按顺序使用第 1、2、3、4 条道路，依次经过补给站 1 → 2 → 3 → 1 → 4，并在补给站 4 供应食物。此路径耗时最短。 第 4 天的补给计划为 2、4、2。由于 JOI-kun 无法执行该计划，输出 -1。 ### 数据范围 所有输入数据满足以下条件： - $2 \le N \le 2\,000$。 - $N - 1 \le M \le 2\,000$。 - $1 \le T \le 100\,000$。 - $2 \le L \le 100\,000$。 - $1 \le A_i < B_i \le N$（$1 \le i \le M$）。 - $(A_i, B_i) \ne (A_j, B_j)$（$1 \le i < j \le M$）。 - 从任意补给站出发，均可经由一条或多条道路抵达其他任意补给站。 - $1 \le C_i \le 1\,000\,000\,000$（$1 \le i \le M$）。 - $1 \le X_j \le N$（$1 \le j \le L$）。 - $1 \le P_k \le L$（$1 \le k \le T$）。 - $1 \le Q_k \le N$（$1 \le k \le T$）。 - 对每个 $j$（$1 \le j \le L - 1$），有 $X_j \ne X_{j+1}$。此外，在每次修改补给计划后，对每个 $j$（$1 \le j \le L - 1$），仍满足 $X_j \ne X_{j+1}$。 ### 子任务 共有 4 个子任务。每个子任务的得分及附加约束如下： **子任务 1 [12 分]** - $N \le 10$。 - $M \le 10$。 - $T = 1$。 - $L \le 10$。 - $C_i \le 10$（$1 \le i \le M$）。 **子任务 2 [35 分]** - $N \le 500$。 - $M \le 500$。 - $T = 1$。 **子任务 3 [15 分]** - $T = 1$。 **子任务 4 [38 分]** 无额外约束。 翻译由 Qwen3-235B 完成