TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3486
  • 题目
  • P3486业务
    限制 : 时间限制 : 30000 MS   空间限制 : 165536 KB
    问题描述

    Mr_H 谋得一份兼职——货车司机,从此以后他将会开着货车穿行在C 国的各大城市之间。
    C 国中有n 座城市(编号为1~n),并且有m 条双向公路,每条公路连接两座不同的城市。货车从任意一座城市出发都可以抵达任意另一座城市。在每条公路上,都有一个收费站,通过的车辆需要交纳一定过路费。可能有多条公路连接相同的两座城市。
    为了增加财政收入,C 国还在每座城市也设置了收费站。并且规定,车辆从一座城市到另一座城市的费用是,所经过公路费用和,加上所经过的城市中费用的次.大.值.(这里的次大可以和最大相同,但是城市不同)。
    现在Mr_H 告诉你今年k 次业务运送货物的起点、终点城市列表,请你帮忙计算,每次业务需要交纳的最低过路费。

    输入格式

    第一行包含三个用一个空格隔开的整数:n,m,k。其意义如题目描述。
    第 2 到第 n+1 行:第i+1 行包含一个单独的整数 c(1<=c<=100000),表示城市i 的费用。接下来的m 行,每行包含三个整数a,b,w,表示一条公路连接城市a 和城市b(1<=a,b<=n),其过路费为w(1<=w<=100000)。
    最后的 k 行,每行包含两个整数:s,t,表示一次业务的起点和终点(1<=s,t<=n 且 s!=t)。

    输出格式

    共k 行,每行一个整数,表示从城市s 到t 的最少过路费。

    样例输入

    5 7 3
    2
    5
    3
    3
    4
    1 2 3
    1 3 2
    2 5 3
    5 3 1
    5 4 1
    2 4 3
    3 4 4
    1 3
    1 4
    2 3

    样例输出

    4
    7
    8

    提示

    【样例说明】
    包含 5 个城市的样例图形如下:

    ●城市1 到城市3 的道路的“边过路费”为 2,“点过路费”为 2(城市2 的费用为次大)。所以总的花费为 2+2=4 。
    ●要从城市1 走到城市4 ,可以从城市1 走到城市3,再走到城市5,最后到达城市4 。如果这么走的话,需要的“边过路费”为 2+1+1=4,需要的点过路费为 3(城市3 或城市4 的点过路费次大),所以总的花费为 4+3=7。
    ●从城市2 走到城市3 的最佳路径是从城市2 出发,抵达城市5,最后到达城市3,这么走的话,边过路费为 3+1=4,点过路费为4,总花费为 4+4=8。
    【数据范围】
    对于 20%的数据,n<=10, m<=20
    对于50%的数据,n<=100, m<=5000
    对于100%的数据,1<=n<=250 , 1<=m<=10000 , 1<=k<=10000 ,其中有50%的数据点权没有重复。


    来源  by YZ