[USACO09JAN]最好的地方Best Spot

题目描述

Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures F\_i of the P (1 <= P <= 500; 1 <= F\_i <= 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. ```cpp 1*--[4]--2--[2]--3 | | [3] [4] | | 4--[3]--5--[1]---6---[6]---7--[7]--8* | | | | [3] [2] [1] [3] | | | | 13* 9--[3]--10*--[1]--11*--[3]--12* ``` The following table shows distances for potential 'best place' of pastures 4, 5, 6, 7, 9, 10, 11, and 12: ```cpp * * * * * * Favorites * * * * * * Potential Pasture Pasture Pasture Pasture Pasture Pasture Average Best Pasture 1 8 10 11 12 13 Distance ------------ -- -- -- -- -- -- ----------- 4 7 16 5 6 9 3 46/6 = 7.67 5 10 13 2 3 6 6 40/6 = 6.67 6 11 12 1 2 5 7 38/6 = 6.33 7 16 7 4 3 6 12 48/6 = 8.00 9 12 14 3 4 7 8 48/6 = 8.00 10 12 11 0 1 4 8 36/6 = 6.00 ** BEST 11 13 10 1 0 3 9 36/6 = 6.00 12 16 13 4 3 0 12 48/6 = 8.00 ``` 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)个牧场.贝茜特别喜欢其中的F个.所有的牧场 由C(1 < C<=8000)条双向路连接,第i路连接着ai,bi,需要Ti(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

13 6 15 
11 
13 
10 
12 
8 
1 
2 4 3 
7 11 3 
10 11 1 
4 13 3 
9 10 3 
2 3 2 
3 5 4 
5 9 2 
6 7 6 
5 6 1 
1 2 4 
4 5 3 
11 12 3 
6 10 1 
7 8 7 

输出样例 #1

10 

说明

As the problem statement As the problem statement.