← 返回题目列表

AtCoder · joi2014ho4

D. 蜜袋鼯

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

配点: 100 点

蜜袋鼯的 JOI 你居住的森林里有桉树。 N 这些树上长着树。 它的编号为 1 如果要将其更改为输出最多为 N 。树 i 的高度是 H_i 这是一米。

JOI 有一群树,你可以直接跳到对方身上。 M 有集合,并且每个集合中的树之间跳跃所需的时间是固定的。 JOI 当你在树间跳跃时,距地面的高度是 1 每秒 1 下降几米。也就是说,JOI君现在距离地面的高度是 h 米,在树间跳跃所需的时间 t 秒,跳跃后距地面的高度为 h - t 变为米。然而, 如果高度小于h - t 是 从 0 或大于目标树的高度,则无法跳跃。

此外,JOI 可以通过上下移动树的侧面来增加距地面的高度。 0 可以在米到当前树的高度范围内增加或减少。 JOI你是离地高度 1 增加或减少米 需要 1 秒。

JOI你是一棵树 1 高度 X 米位置的树 N 的顶部(高度 H_N 米)并想知道完成此操作所需的最短时间。

課題

给出了每棵树的高度、JOI可以直接跳转到的树集合信息以及JOI最初所在位置的高度。树 编写一个程序来找出到达 N 顶部所需的最短时间。


入力

从标准输入读取以下数据。

  • 1 行包含一个整数 N, M, X 以空格作为分隔符。这意味着树的数量是 N 一本书,一套可移动的树 M 有组,先JOI君 1 高度 X 表示处于米的位置。
  • 继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 H_i 。这是一棵树 i 的高度是 H_i 代表米。
  • 继续 M 行 j 行目 (1 \leqq j \leqq M) 是一个整数 写入 A_j, B_j, T_j (1 \leqq A_j \leqq N,1 \leqq B_j \leqq N,A_j \neq B_j)以空格作为分隔符。这是一棵树 A_j 和树 B_j 之间相互 这意味着您可以在 T_j 秒内从一个地方跳到另一个地方。另外,1 \leqq j < k \leqq M 然后,(A_j, B_j) \neq (A_k, B_k) 和 (A_j, B_j) \neq (B_k, A_k) 很满意。

出力

该树打印在标准输出上。 1 高度 X 米位置的树 N 是一个整数,表示到达顶部所需的最短时间(以秒为单位)。 输出为 1 行。但是,如果没有这样的方法,而是 输出 -1 。


制限

所有输入数据满足以下条件。

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 300\,000.
  • 1 \leqq H_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq T_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq M).
  • 0 \leqq X \leqq H_1.

小課題

小課題 1 [25 点]

满足以下条件。

  • N \leqq 1\,000.
  • M \leqq 3\,000.
  • H_i \leqq 100 (1 \leqq i \leqq N).
  • T_j \leqq 100 (1 \leqq j \leqq M).

小課題 2 [25 点]

满足以下条件。

  • X = 0.

小課題 3 [50 点]

没有其他限制。


入力例 1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

出力例 1

110

例如,您可以按如下方式移动。

  1. 木 1 从 50 爬升米。
  2. 木 1 卡拉树 跳转至 2 。
  3. 木 2 卡拉树 跳转至 4 。
  4. 木 4 卡拉树 跳转至 5 。
  5. 木 5 从 10 爬升米。

入力例 2

2 1 0
1
1
1 2 100

出力例 2

-1

JOI你是一棵树 您无法跳至 1 卡拉树 跳转至 2 。


入力例 3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

出力例 3

100