/ TYWZ / 题库 /

过路费

过路费

【问题描述】
有一天你来到了一个奇怪的国家,它有N个城市,城市之间有若干条双向道路连接,每条道路都有一定的费用,经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用(包括起点和终点)加上路径上所有的道路的费用。给出Q次询问,分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。
【输入格式】
第一行两个整数N,M,表示有N个城市M条道路。
接下来N行每行一个整数,表示城市的费用ci。
接下来M行每行三个整数,x,y,z,表示城市x和城市y间有一条费用为z的道路。
接下来一行一个整数Q,表示询问次数。
接下来Q行每行两个整数x,y(x不等于y),表示询问从城市x到城市y的最小花费。
【输出格式】
共Q行每行一个整数,第i行的整数表示第i次询问的答案。
【样例输入】
3 3
1
3
2
1 2 1
2 3 1
1 3 3
2
1 3
1 3
【样例输出】
5
5
【数据规模】
对于30%的数据,N<=10,M<=20,Q<=5。
对于60%的数据,N<=200,M<=4000,Q<=100。
对于100%的数据,N<=300,M<=40000,Q<=100000,1<=ci<=100000,1<=z<=1000。

信息

ID
1036
难度
7
分类
(无)
标签
(无)
递交数
75
已通过
12
通过率
16%
上传者