#2759. 「JOI 2014 Final」飞天鼠

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

题目描述

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

飞天鼠 JOI 君住着的森林里长着编号为 11NNNN 棵桉树。第 ii 棵树的高度是 HiH_{i} 米。

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

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

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

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

输入格式

第一行包含三个以空格分开的整数 N,MN, MXX,意义分别与题目描述中的 N,MN, MXX 相同。
接下来 NN 行中,第 i(1iN)i(1\le i\le N) 行有一个整数 HiH_{i},表示树木ii的高度是 HiH_{i} 米。
接下来 MM 行中,第 j(1jM)j(1\le j\le M) 行有三个以空格分开的整数 Aj,Bj,TjA_{j},B_{j},T_{j} (1Aj,BjN,(1\le A_{j}, B_{j}\le N, AjBj)A_{j}\ne B_{j}),表示 IOI 君能花 TjT_{j} 秒的时间从 AjA_{j} 飞到 BjB_{j} 或从 BjB_{j} 飞到 AjA_{j}
对于任意 1j<kM1\le j < k\le M,满足 (Aj,Bj)(Ak,Bk)(A_{j},B_{j})\neq (A_{k},B_{k})(Aj,Bj)(Bk,Ak)(A_{j},B_{j})\neq (B_{k},A_{k})

输出格式

输出到标准输出,仅一行一个整数,表示从树木 11 上高度为 XX 米处移动到树木 NN 顶端所需时间的最小值(单位:秒)。如果不能到达目的地则输出 1-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. 沿着树木 11 向上爬 5050 米。
  2. 从树木 11 飞到树木 22
  3. 从树木 22 飞到树木 44
  4. 从树木 44 飞到树木 55
  5. 沿着树木 55 向上爬 1010 米。

输入样例 2

2 1 0
1
1
1 2 100

输出样例 2

-1

样例解释 2

JOI 君无法从树木 11 飞到树木 22

输入样例 3

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

输出样例 3

100

数据范围与提示

全部的输入数据满足:

  • 2N1000002\le N\le 100000
  • 1M3000001\le M\le 300000
  • 1Hi109(1iN)1\le H_{i}\le 10^{9}(1\le i\le N)
  • 1Tj109(1jM)1\le T_{j}\le 10^{9}(1\le j\le M)
  • 0XH10\le X\le H_{1}

子任务 1(25 分)

满足以下条件:

  • N1000N\le 1000
  • M3000M\le 3000
  • Hi100(1iN)H_{i}\le 100(1\le i\le N)
  • Tj100(1jM)T_{j}\le 100(1\le j\le M)

子任务 2(25 分)

满足 X=0X=0

子任务 3(50 分)

没有额外限制。