TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2355
  • 题目
  • P2355【NOIP无压力模拟赛1】Path
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Loongint非常喜欢Dota这款游戏~但是他总是被Dota复杂的地图困扰,有时候甚至会因为地图太复杂而失去了自己Gank和Farm的节奏。所以他需要你的帮忙。

    地图上一共有n个关键位置,每个关键位置有一个关键值Vi, 关键位置之间有m条双向的通路,每条通路有其通行值Ci,我们定义两关键位置之间的距离为其间的通路的通行值和加上路径上关键值最大的关键位置(包括起点终点)的关键值。

    Loongint现在有Q个询问,对于每个询问,你需要告诉他a关键位置和b关键位置间的最短距离。

    输入格式

    第1行为三个数 n,m,q,
    第2行到第n+1行表示关键位置的关键值Vi,
    第n+2到第n+m+1行表示通路的起始位置和通行值,
    第n+m+2到第n+m+q+1行表示q个询问,每个询问给出a,b。

    输出格式

    输出q行,每行对应一个询问的最短距离。

    样例输入

    5 7 2 











    1 2 3 

    1 3 2 

    2 5 3 

    5 3 1 

    5 4 1 

    2 4 3 

    3 4 4 

    1 4 

    2 3 

    样例输出


    9

    提示

    N≤250,M≤10,000

    Q≤10,000;Vi,Ci≤100,000


    来源  HZOI