P13515 [KOI 2025 #1] 木槿花开了

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 村庄由 $N$ 个建筑和 $M$ 条道路组成。 建筑从 1 到 $N$ 编号，每个建筑可能有也可能没有窗户。对于 $1 \le i \le N$ 的每个 $i$，如果第 $i$ 个建筑有窗户，则 $c_i=1$，如果没有窗户，则 $c_i=0$。规定第 1 个建筑和第 $N$ 个建筑没有窗户，即 $c_1 = c_N = 0$。 道路从 1 到 $M$ 编号，每条道路都是连接一个起始建筑和一个到达建筑的单向通道。对于 $1 \le j \le M$ 的每个 $j$，第 $j$ 条道路从建筑 $x_j$ 开始，到建筑 $y_j$ 结束，通过这条道路需要花费恰好 $t_j$ 秒。因为是单向道路，所以不能逆向行驶（即，从建筑 $y_j$ 移动到建筑 $x_j$）。 在 KOI 村庄，Hankook 和 Jeong-ul 打算玩一个基于“木槿花开了”游戏改编的以下游戏。 游戏开始时，Jeong-ul 在 1 号建筑。Jeong-ul 的目标是在不被 Hankook 的视线发现一次的情况下，尽可能快地到达 $N$ 号建筑。相反，Hankook 的目标是在 Jeong-ul 到达 $N$ 号建筑之前找到他。 Hankook 睁着眼时可以看到整个 KOI 村庄，但无法看到没有窗户的建筑内部。也就是说，Hankook 只能看到有窗户的建筑内部和所有道路。 Hankook 从游戏开始（0 秒）时起，周期性地重复以下动作： * 首先，闭上眼睛恰好 $a$ 秒。 * 紧接着，睁开眼睛并观察村庄恰好 $b$ 秒。 * 此过程无限重复。 我们可以将上述过程用数学公式严格地表达如下： * 我们定义“从游戏开始时经过的时间”为 $t$（以秒为单位）。 * 当时间 $t = k(a+b) + l$ 时（其中 $k$ 为非负整数， $l$ 为满足 $0 \le l < a+b$ 的实数）： * 如果 $0 \le l < a$，Hankook 闭着眼睛。 * 如果 $a \le l < a+b$，Hankook 睁着眼睛。 * 也就是说，对于非负整数 $k$，Hankook 闭眼的时间是闭区间 $[k(a+b), k(a+b)+a]$，睁眼的时间是开区间 $(k(a+b)+a, (k+1)(a+b))$。 Jeong-ul 从游戏开始的时刻（0 秒）起，可以随时开始移动，并且在建筑内部（无论是否有窗户）等待和移动都是自由的，不消耗时间。从建筑出来或进入建筑内部也不消耗时间。如果 Jeong-ul 开始沿着某条道路移动，他必须花费该道路所需的确切时间来移动，并且在移动过程中不能在道路上停下或等待。移动结束后，他将到达道路的终点建筑。 Jeong-ul 被 Hankook 发现的基准如下： * 在 Hankook 睁着眼的时候，如果 Jeong-ul 位于道路上或在有窗户的建筑内部，他会立即被发现，游戏随之结束。因此，在 Hankook 睁着眼的时间段内，Jeong-ul 必须位于没有窗户的建筑内。 * 在 Hankook 闭着眼的时候，无论 Jeong-ul 在哪里，都绝对不会被发现。 * 请注意，如果 Jeong-ul 进入没有窗户的建筑的时刻，恰好是 Hankook 开始睁眼的瞬间；或者他进入道路开始移动的时刻，恰好是 Hankook 开始闭眼的瞬间，则不会被发现。 在这些条件下，请编写一个程序，判断 Jeong-ul 是否有可能在不被 Hankook 发现一次的情况下安全到达 $N$ 号建筑，如果可能，计算 Jeong-ul 到达 $N$ 号建筑所需的最短时间（以秒为单位）。

第一行给出两个整数 $N$ 和 $M$，以空格分隔。 接下来的 $M$ 行给出道路的信息。其中第 $j$ ($1 \le j \le M$) 行包含三个整数 $x_j, y_j, t_j$，以空格分隔。 再下一行给出 $N$ 个整数 $c_1, c_2, \cdots, c_N$，以空格分隔。 最后一行给出两个整数 $a, b$，以空格分隔。

如果无论 Jeong-ul 如何移动都无法到达 $N$ 号建筑，则输出 `-1`。 否则，输出 Jeong-ul 到达 $N$ 号建筑所需的最短时间（以秒为单位）。可以证明，这个值总是一个整数。

### 样例 1 解释 随着时间的推移，Jeong-ul 和 Hankook 可以按如下方式行动： * 0 秒 - 3 秒：Hankook 闭着眼睛。Jeong-ul 在 0 秒时进入 1 号道路（1 号建筑 → 2 号建筑），并于 3 秒时到达 2 号建筑。 * 3 秒 - 11 秒：Hankook 在 3 秒时睁开眼睛。Jeong-ul 在 2 号建筑一直停留到 11 秒。 * 11 秒 - 14 秒：Hankook 在 11 秒时闭上眼睛。Jeong-ul 在 11 秒时进入 3 号道路（2 号建筑 → 4 号建筑），并于 14 秒时到达 4 号建筑。 由于 Jeong-ul 没有比 14 秒更快到达 4 号建筑的方法，因此应当输出 14。 ### 样例 2 解释 由于除 1 号和 4 号建筑外的所有建筑都有窗户，Jeong-ul 必须在 Hankook 睁开眼睛之前（即，在 $a=3$ 秒内）到达 4 号建筑。但是，Jeong-ul 不可能在 3 秒内到达 4 号建筑。因此，应当输出 `-1`。 ### 限制条件 * 给定的所有数都是整数。 * $3 \le N \le 2000$ * $3 \le M \le 4000$ * 对于每个 $1 \le j \le M$ 的 $j$，有 $1 \le x_j, y_j \le N, x_j \ne y_j, 1 \le t_j \le 100,000$。 * 对于 $1 \le j < k \le M$ 的任意 $j, k$，有 $(x_j, y_j) \ne (x_k, y_k)$。也就是说，所有道路的起点和终点对都是唯一的。 * 对于 $2 \le i \le N-1$ 的每个 $i$，$c_i \in \{0, 1\}$。 * $c_1 = c_N = 0$。即，1 号建筑和 $N$ 号建筑没有窗户。 * $1 \le a, b \le 10^9$。 ### 子任务 1. (12 分) $N \le 5, M \le 10$。 2. (19 分) 对于 $2 \le i \le N-1$ 的每个 $i$，$c_i=1$。 3. (31 分) 对于 $1 \le j \le M$ 的每个 $j$，$t_j=1$。 4. (27 分) $M=N-1$。并且，对于 $1 \le j \le N-1$ 的每个 $j$，$x_j = j, y_j = j+1$。 5. (61 分) 无附加限制条件。