TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4265
  • 题目
  • P4265过路费
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    有一天你来到了一个奇怪的国家,它有 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 次询问的答案。

    样例输入

    33

    1

    3

    2

    12 1

    23 1

    13 3

    2

    13

    13

    样例输出

    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。