TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4265
  • Problem
  • P4265过路费
    Limits : Time Limit : - MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

    有一天你来到了一个奇怪的国家,它有 N 个城市,城市之间有若干条双向道路连接,每条道路都有一定的费用,经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用(包括起点和终点)加上路径上所有的道路的费用。给出 Q 次询问,分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。

    Input Format

    第一行两个整数 N,M,表示有 N 个城市 M 条道路。

     

    接下来 N 行每行一个整数,表示城市的费用 ci。

     

    接下来 M 行每行三个整数,x,y,z,表示城市 x 和城市 y 间有一条费用为 z 的道路。

     

    接下来一行一个整数 Q,表示询问次数。

     

    接下来 Q 行每行两个整数 x,y(x 不等于 y),表示询问从城市 x 到城市 y 的最小花费。

    Output Format

    共 Q 行每行一个整数,第 i 行的整数表示第 i 次询问的答案。

    Sample Input

    3 3

    1

    3

    2

    1 2 1

    2 3 1

    1 3 3

    2

    1 3

    1 3

    Sample Output

    5
    5

    Hint

    数据规模】

     

    对于 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。