当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1619:迷宫的阿狸再续

题目描述
阿狸被抓走啦,snoopy又要去救他。
现在snoopy拿到一张迷宫地图,地图上有n个结点,有m条双向的路连接着这n个结点。
snoopy是从1号结点出发的,而阿狸被关在n号结点。
每条路都有过路费,一旦经过就要支付一定数量的金钱;此外各个结点都驻守着强盗,一旦snoopy到达该结点那么snoopy就会被抢走一定数量的金钱。
为了营救阿狸,snoopy想知道最少会损失多少钱?
输入解释
多组数据
每行两个整数n、m(1<=n<=100000, 1<=m<=100000)
然后一行有n个数ai,表示到达i城市会被抢走的钱数(1<=ai<=10000)
接下去m行,每行三个整数u、v、w,表示u和v之间有一条双向路,且过路费为w(1<=u,v<=n, 1<=w<=10000)
输出解释
输出最少损失的钱
输入样例
2 1
10 10
1 2 10

3 3
10 10 10
1 2 1
2 3 1
1 3 10000
输出样例
30
32

该题目包含在题集 ACM赛制

题目来源 WABoss@FAFU

共提交 45

通过率 13.33%
时间上限 内存上限
2000 MS 128 MB