BEST SPOT
题目描述
Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures FiF_iFi of the P(1<=P<=500;1<=Fi<=P)P (1 <= P <= 500; 1 <= F_i <= P)P(1<=P<=500;1<=Fi <=P) total pastures (conveniently
numbered 1..P) that compose Farmer John's holdings.
Bessie knows that she can navigate the C (1 <= C <= 8,000) bidirectional cowpaths (conveniently numbered 1..C) that connect various pastures to travel to any pasture on the entire farm. Associated with each path P_i is a time T_i (1 <= T_i <= 892) to traverse that path (in either direction) and two
path endpoints a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P).
Bessie wants to find the number of the best pasture to sleep in so that when she awakes, the average time to travel to any of her F favorite pastures is minimized.
By way of example, consider a farm laid out as the map below shows, where *'d pasture numbers are favorites. The bracketed numbers are times to traverse the cowpaths.
The following table shows distances for potential 'best place' of pastures 4, 5, 6, 7, 9, 10, 11, and 12:
Thus, presuming these choices were the best ones (a program would have to check all of them somehow), the best place to sleep is pasture 10.
约翰拥有 P(1<=P<=500)P(1<=P<=500)P(1<=P<=500) 个牧场.贝茜特别喜欢其中的F个.所有的牧场 由 C(1<C<=8000)C(1 < C<=8000)C(1<C<=8000) 条双向路连接，第 iii 路连接着ai,bia_i,b_iai ,bi ，需要 TiT_iTi (1<=Ti<892)(1<=T_i< 892)(1<=Ti <892) 单 位时间来通过.
作为一只总想优化自己生活方式的奶牛，贝茜喜欢自己某一天醒来，到达所有那F个她喜欢的 牧场的平均需时最小.那她前一天应该睡在哪个牧场呢？请帮助贝茜找到这个最佳牧场.
此可见，牧场10到所有贝茜喜欢的牧场的平均距离最小，为最佳牧场.
输入格式
* Line 1: Three space-separated integers: P, F, and C
* Lines 2..F+1: Line i+2 contains a single integer: F_i
* Lines F+2..C+F+1: Line i+F+1 describes cowpath i with three
space-separated integers: a_i, b_i, and T_i
输出格式
* Line 1: A single line with a single integer that is the best pasture in which to sleep. If more than one pasture is best, choose the smallest one.
样例 #1
样例输入 #1
样例输出 #1
提示
As the problem statement
As the problem statement.
