#2759. 「JOI 2014 Final」飞天鼠

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fbhou

题目描述

译自 JOI 2014 Final T4「フクロモモンガ

飞天鼠 JOI 君住着的森林里长着编号为 1 N N 棵桉树。第 i 棵树的高度是 H_{i} 米。

JOI 君能在其中的 M 对桉树之间直接飞行,在各对树木之间飞行所需的时间是固定的。当 JOI 君在树木之间飞行的时候,他离地面的高度会每秒下降 1 米。也就是说,如果 JOI 君现在离地高度是 h 米,在树木之间飞行需要 t 秒,那么飞行之后的离地高度就会变成 h-t 米。当 h-t 小于 0 或大于目标树木的高度时则不能飞行。

JOI 君还能沿着树的侧面上下移动,使得他的离地高度在 0 到当前所在树木高度的范围内变化。JOI 君每使自己的离地高度增加或减少 1 米都需要 1 秒的时间。

JOI 君要从 1 号树木上高度为 X 米的位置出发,到树木 N 的顶端(高度为 H_{N} 米的位置)去。他想知道为了达成这个目标所需时间的最小值。

给出各棵树木的高度、JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度,请求出到达树木 N 顶端所需时间的最小值。

输入格式

第一行包含三个以空格分开的整数 N, M X ,意义分别与题目描述中的 N, M X 相同。
接下来 N 行中,第 i(1\le i\le N) 行有一个整数 H_{i} ,表示树木 i 的高度是 H_{i} 米。
接下来 M 行中,第 j(1\le j\le M) 行有三个以空格分开的整数 A_{j},B_{j},T_{j} (1\le A_{j}, B_{j}\le N, A_{j}\ne B_{j}) ,表示 IOI 君能花 T_{j} 秒的时间从 A_{j} 飞到 B_{j} 或从 B_{j} 飞到 A_{j}
对于任意 1\le j < k\le M ,满足 (A_{j},B_{j})\neq (A_{k},B_{k}) (A_{j},B_{j})\neq (B_{k},A_{k})

输出格式

输出到标准输出,仅一行一个整数,表示从树木 1 上高度为 X 米处移动到树木 N 顶端所需时间的最小值(单位:秒)。如果不能到达目的地则输出 -1

样例

输入样例 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. 沿着树木 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

样例解释 2

JOI 君无法从树木 1 飞到树木 2

输入样例 3

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

输出样例 3

100

数据范围与提示

全部的输入数据满足:

  • 2\le N\le 100000
  • 1\le M\le 300000
  • 1\le H_{i}\le 10^{9}(1\le i\le N)
  • 1\le T_{j}\le 10^{9}(1\le j\le M)
  • 0\le X\le H_{1}

子任务 1(25 分)

满足以下条件:

  • N\le 1000
  • M\le 3000
  • H_{i}\le 100(1\le i\le N)
  • T_{j}\le 100(1\le j\le M)

子任务 2(25 分)

满足 X=0

子任务 3(50 分)

没有额外限制。