UOJ Logo

NOI.AC

1S 512MB

#2058. 小游戏

Statistics

问题描述

有一个简单的小游戏。游戏的主人公是一个勇士,他要穿过一片黑森林,去解救公主。

黑森林的地图可以用一张$V$个点、$E$条边的无向图来描述,起点是$1$号点,终点是$V$号点,通过每条边的时间均为一

图的边上有荆棘毒刺,而点上有供休憩的小木屋,勇士每一次经过一条边会损失一定的$HP$,每一次到达一个点则会加上一定的$HP[i]$。

当$HP \leq 0$时,勇士死亡;$HP$的上限为$M$,当某一次休憩后$HP \gt M$时,$HP$将只能保留$M$。

勇士要从起点出发,出发时$HP$为$M$,在保证存活的前提下,尽快地到达目的地。

输入格式

第一行三个整数,$V$、$E$、$M$。

第二行$V$个整数,表示每个点每经过一次增加的HP值。

接下来$E$行,每行三个整数$x$、$y$、$z$,表示$x$号点到$y$号点有一条边,每经过一次消耗$z$的$HP$。

输出格式

一行一个整数,表示到达终点的最少时间。若无法到达,则输出-1

样例输入

5 5 3
3 2 3 2 3
1 5 4
1 2 1
2 3 2
3 4 1
4 5 2

样例输出

4

样例解释

走路径1——2——3——4——5

数据规模

测试点编号 V= E= M= z∈ HP[i]∈
1 5 10 10 [0,20] [0,3]
2 5 10 10 [0,20] [0,3]
3 5 10 10 [0,20] [0,3]
4 20 50 20 [0,40] [0,10]
5 100 500 20 [0,40] [0,10]
6 500 1000 500 [0,500] [0,200]
7 1000 5000 1000 [0,3000] [0,200]
8 10000 50000 10000 [0,10000] [0,100]
9 30000 100000 20000 [0,20000] [0,100]
10 30000 100000 20000 [0,20000] [0,100]

对于$100\%$的数据,保证图结构随机生成,保证$z$和$HP[i]$在对应范围内随机生成。