网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[河南省队2012]长途奔袭
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | YZ.in | 输出文件 | YZ.out |
小k所属的联盟PIBC马上要与粉红鱼雷开战了。就在大家准备急行军到战场埋伏粉红鱼雷的时候,小k所属联盟下某TT驾驶员手滑,单独跃迁到了一个不知名的星域并且误入虫洞。
时间不等人,舰队指挥要求这名TT驾驶员立刻返回战场。然而,这名驾驶员所在星域距离战场十分遥远,他位于虫洞入口,需要路过N颗行星。这N颗行星之间有M条双向航道。TT驾驶员为了在最短的时间内赶回战场并侦查附近星域,在航道上,对与这N颗行星,每颗恰好只路过一次。在航道上TT驾驶员有两种前行的方式。一种叫做跃迁,可以瞬间到达下一个地点,但是需要花一定的时间调整转向。另外一种当然就是慢慢爬过去了。但是,由于TT的质量及惯性修正值极大,因此TT在慢慢爬的时候只能向引力更大的行星行驶。但是这名TT驾驶员很笨,不知道该如何规划路线,因此他找到了宇宙中最聪明你帮他规划路线,使他用最少的时间到达战场。
Input
第一行是两个正整数 N, M。 第二行 N 个数 A1~AN,其中Ai表示使用跃迁到达行星 i 所需的转向时间。接下来 M行,每行 3个正整数ui, vi, wi,表示在编号为 ui和vi的行星之间存在一条需要航行wi时间的星际航路。输入数据已经按引力值排序,也就是编号小的行星引力值一定小,且不会有两颗行星引力值相同。
Output
仅包含一个正整数,表示到达战场所需的最少时间。
样例:
YZ.in
3 3
100 1 100
2 1 10
1 3 1
2 3 1
YZ.out
102
对于 30%的数据 N≤20,M≤50;
对于 70%的数据 N≤200,M≤4000;
对于100%的数据N≤800, M≤15000。
输入数据中的任何数都不会超过10^6。
输入数据保证任意两颗行星之间至多存在一条航道,且不会存在某颗行星到自己的航道。