OpenJudge

E04S02:sophie的自驾游

总时间限制:
5000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述

sophie决定暑假出去自驾游。sophie的地图上有N个城市,M条道路,每条道路连接着两个城市,且对应一个过路费w。现在sophie想要从a城市到b城市,但是她的小汽车需要在途中(包括a和b两个城市)加一次油。在每个城市加油都有不同的费用g。sophie想知道从a城市到b城市最少需要多少费用(过路费+加油费)。

输入
第一行两个正整数M,M,表示N个城市,M条无向道路
接下来1行包含N个整数,表示每个城市的加油费用g
接下来M行,每行包含3个整数{u,v,w},表示1条连接u和v的道路,过路费为w
接下来一个正整数Q,表示有Q组询问
接下来Q行,每行包含2个整数{u,v},表示sophie想知道从u到v需要的最少费用(u和v可能相等)
*输入可能包含重边/自环
输出
对于每个询问,输出一行整数,表示最小的费用;如果u不能到达v,则输出-1
样例输入
3 6
2666
3977
2457
1 2 6920
1 2 276
1 3 839
3 1 3490
2 1 7395
3 1 7540
6
3 2
3 1
2 2
2 1
3 2
2 2
样例输出
3572
3296
3218
2942
3572
3218
提示
*对于40%的数据,N <=10, M <= 100, Q = 1;
*对于80%的数据,N <=300, M <= 10000, Q <= 10;
*对于100%的数据,N <=300, M <= 10000, Q <= 10000;
全局题号
15862
添加于
2017-08-11
提交次数
4
尝试人数
2
通过人数
1