#P2966. [USACO09DEC] Cow Toll Paths G

[USACO09DEC] Cow Toll Paths G

题目描述

Like everyone else, FJ is always thinking up ways to increase his revenue. To this end, he has set up a series of tolls that the cows will pay when they traverse the cowpaths throughout the farm.

The cows move from any of the N(1N250)N (1 \leq N \leq 250) pastures conveniently numbered 1...N1...N to any other pasture over a set of M(1M10,000)M (1 \leq M \leq 10,000) bidirectional cowpaths that connect pairs of different pastures AjA_j and Bj(1AjN;1BjN)B_j (1 \leq A_j \leq N; 1 \leq B_j \leq N). FJ has assigned a toll Lj(1Lj100,000)L_j (1 \leq L_j \leq 100,000) to the path connecting pastures AjA_j and BjB_j.

While there may be multiple cowpaths connecting the same pair of pastures, a cowpath will never connect a pasture to itself. Best of all, a cow can always move from any one pasture to any other pasture by following some sequence of cowpaths.

In an act that can only be described as greedy, FJ has also assigned a toll Ci(1Ci100,000)C_i (1 \leq C_i \leq 100,000) to every pasture. The cost of moving from one pasture to some different pasture is the sum of the tolls for each of the cowpaths that were traversed plus a single additional toll that is the maximum of all the pasture tolls encountered along the way, including the initial and destination pastures.

The patient cows wish to investigate their options. They want you to write a program that accepts K(1K10,000)K (1 \leq K \leq 10,000) queries and outputs the minimum cost of trip specified by each query. Query ii is a pair of numbers sis_i and $t_i (1 \leq s_i \leq N; 1 \leq t_i \leq N; s_i \neq t_i)$ specifying a starting and ending pasture.

Consider this example diagram with five pastures:

The 'edge toll' for the path from pasture 11 to pasture 22 is 33. Pasture 22's 'node toll' is 55.

To travel from pasture 11 to pasture 44, traverse pastures 11 to 33 to 55 to 44. This incurs an edge toll of 2+1+1=42+1+1=4 and a node toll of 44 (since pasture 55's toll is greatest), for a total cost of 4+4=84+4=8.

The best way to travel from pasture 22 to pasture 33 is to traverse pastures 22 to 55 to 33. This incurs an edge toll of 3+1=43+1=4 and a node toll of 55, for a total cost of 4+5=94+5=9.

给定一个 nnmm 边的双向图,第 ii 条道路连接了 uiu_iviv_i,边权为 wiw_i,第 ii 个点的点权为 cic_i

给定 qq 组询问,第 ii 组询问求从 sis_itit_i 的路径的边权之和与点权的最大值的和的最小值。

可能有重边,但保证无自环。

输入格式

  • Line 11: Three space separated integers: NN, MM, and KK

  • Lines 2..N+12..N+1: Line i+1i+1 contains a single integer: CiC_i

  • Lines N+2..N+M+1N+2..N+M+1: Line j+N+1j+N+1 contains three space separated integers: AjA_j, BjB_j, and LjL_j

  • Lines N+M+2..N+M+K+1N+M+2..N+M+K+1: Line i+N+M+1i+N+M+1 specifies query ii using two space-separated integers: sis_i and tit_i

第一行三个整数 n,m,qn,m,q 代表点数,边数与询问数。
接下来 nn 行每行一个整数 cic_i 代表第 ii 个点的点权。
接下来 mm 行每行三个整数 ui,vi,wiu_i,v_i,w_i 代表第 ii 条边从 uiu_i 连到 viv_i 边权为 wiw_i
接下来 qq 行每行两个整数 si,tis_i,t_i 代表第 ii 组询问求从 sis_itit_i 的边权之和与点权的最大值的和的最小值。

输出格式

  • Lines 1..K1..K: Line ii contains a single integer which is the lowest cost of any route from sis_i to tit_i

qq 行每行一个整数,代表第 ii 组询问的结果。

5 7 2 
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 4 
2 3 

8 
9 

提示

对于 100%100\% 的数据,1n2501 \le n \le 2501m1041 \le m \le 10^41q1041 \le q \le 10^4