/ Vijos / 题库 /

ファーラの力

ファーラの力

背景

窗外斜阳 日暮西山 倚栏眺
想着当年气盛青涩的年少
时光湍急 岁月汹涌 物是人已非
年年我挥汗洒泪赴沙场

描述

Ninian 的魔力可以在结界间传递。
结界中有 N 个光柱,第 i 个光柱的光压范围为 0~Ei 。魔力可以有 M 种传递,从光柱 Ai 传递到光柱 Bi ,花费时间 Ti 。
当魔力从光压为 S 传递并花费了 T 的时间后,就会衰减到光柱上光压为 S-T 处,S-T 不能为负。
Ninian 可以将魔力的光压花费 1 时间增加 1 或减少 1 ,当然魔力的光压不能超过光柱的光压范围,也不能小于 0 。
Ninian 的魔力初始在 1 号光柱,光压为 X 。
问 Ninian 的魔力到达第 N 个光柱且光压最大所需要的最少时间。

格式

输入格式

第一行三个整数 N, M, X 。
接下来的 N 行每行一个整数表示 Ei 。
接下来的 M 行每行三个整数表示 Ai, Bi, Ti 。

输出格式

输出一个整数表示所需的最少时间,如果 Ninian 的魔力无法到达,输出 -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

样例2

样例输入2

2 1 0
1
1
1 2 100

样例输出2

-1

样例3

样例输入3

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

样例输出3

100

限制

2 ≤ N ≤ 100 000.
1 ≤ M ≤ 300 000.
1 ≤ Ei ≤ 1 000 000 000.
1 ≤ Ti ≤ 1 000 000 000.
0 ≤ X ≤ H1.

对于 20% 的数据:
N ≤ 1 000.
M ≤ 3 000.
Hi ≤ 100.
T ≤ 100

对于另外 40% 的数据: X = 0.

提示

样例1解释:
光柱1: 花费 50 时间将光压加到 50 。
1->2->4->5 花费 50 时间,光压=50-50=0
光柱5: 花费 10 时间将光压加到 10 ,达到光柱 5 所能承受最大光压,总花费 110 。

来源

布吉岛。

信息

ID
1880
难度
8
分类
(无)
标签
(无)
递交数
367
已通过
44
通过率
12%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Deplore NOIP模拟赛