← 返回题目列表

AtCoder · joi2017yo_f

F. 蛇 JOI

中文机器翻译题面 查看原题

配点: 100 点

問題

蛇 JOI 你走进了一座大宅邸。你必须在宅邸的居民找到你之前逃离宅邸。

这座宅邸里有房间。 N 可用, 它的编号为1, 2, \ldots, N 。还有,走廊 M 书籍可用,i 主走廊(1 \leqq i \leqq M) 是房间 A_i 和房间 B_i 已连接。 JOI 你可以从任何一个方向穿过这些走廊,并且 通过 i 需要 D_i 分钟。除了通过走廊之外,无法在房间之间移动。

这座宅邸的每个房间的温度都被调节到一个恒定的水平,对于你来说,要么太冷,要么太舒服,要么太热,JOI。由于JOI君无法应对突然的温度变化,自从上次离开太冷的房间以来,他就一直无法应对突然的温度变化。 您不能进入太热的房间并持续时间少于 X 分钟。同样,自从您上次离开太热的房间以来, X 我什至无法进入一个太冷的房间不到一分钟。

JOI 如果您在移动时进入房间,则必须立即离开该房间。另外,如果您在走廊中途折回或 行驶时间不可能超过 i 在 D_i 分钟。但是,您可以重新进入您已经访问过的房间或使用您之前使用过的走廊。

JOI 您目前在房间里 我在 1 。这个房间对你来说太冷了,JOI。 JOI 你是豪宅出口的房间 你可以通过输入 N 逃离宅邸。

JOI 找出你逃离宅邸所需的最短时间。 在


入力

输入是 有一行 1 + N + M 行.

1 行中,3 整数 给出 N, M, X (2 \leqq N \leqq 10\,000,1 \leqq M \leqq 20\,000,1 \leqq X \leqq 200)以空格作为分隔符。这是一座豪宅 N 房间和 M 走廊里摆满了书,JOI君对温度变化做出反应。 表示需要 X 分钟。

继续 N 行中的 i 行目 (1 \leqq i \leqq N) 有房间 表示 i 温度的整数 T_i (0 \leqq T_i \leqq 2)被写入。 JOI房间给你 i 是T_i = 0 时太冷了T_i = 1 时很舒服T_i = 2 时太热了。T_1 = 0 有保证。

继续 M 行中的 j 行目 (1 \leqq j \leqq M)有3 整数 给出 A_j, B_j, D_j (1 \leqq A_j < B_j \leqq N,1 \leqq D_j \leqq 200)以空格作为分隔符。这是走廊 j 是房间 A_j 和房间 B_j 表示需要 D_j 分钟。请注意,可能有多个走廊连接同一组房间。

给出输入数据后,JOI 就可以逃出宅邸。

出力

JOI 输入一个整数,表示您逃离宅邸所需的最短分钟数。 输出为 1 行。


入力例 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

出力例 1

9

入力例 1 现在,让我们看看房间。 最短的方法是按照 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8 的顺序移动。 在


入力例 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

出力例 2

6

入力例 2 中,某些房间组(例如 有多个走廊连接 1 和房间 5)。