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

·

·

·

·

登陆或注册以提交代码