P2935 [USACO09JAN] Best Spot S
题目描述
约翰拥有 $P(1 \leq P \leq 500)$ 个牧场，
贝茜特别喜欢其中的 $F(1\leq F \leq P)$ 个。
所有的牧场由 $C(1 < C \leq 8000)$ 条双向路连接，第 $i$ 条路连接着 $a_i$,$b_i$ 两个牧场 $(1 \leq a_i \leq P,1 \leq b_i \leq P)$，需要 $T_i(1 \leq T_i < 892)$ 个单位时间来通过。
作为一只总想提升自己生活方式的奶牛，贝茜希望自己有朝一日醒来，到达所有那 $F$ 个她喜欢的牧场的平均用时最小。那她前一天应该睡在哪个牧场呢？请帮助贝茜找到这个最佳牧场。
例如，考虑如下图所示的牧场布局，其中含有 * 的牧场的编号是最受欢迎的。而中括号内的数字是这条牛道的通过时间。
```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*
```
下表显示了牧场 $4,5,6,7,9,10,11$ 和 $12$ 与贝茜最喜欢的牧场的各个距离、平均距离和最终求出的最佳牧场：
```cpp
* * * * * * 最喜欢的牧场 * * * * * *
可能的 牧场 牧场 牧场 牧场 牧场 牧场 平均
最佳牧场 1 8 10 11 12 13 距离
------------ -- -- -- -- -- -- -----------
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 ** 最佳的
11 13 10 1 0 3 9 36/6 = 6.00
12 16 13 4 3 0 12 48/6 = 8.00
```
由表格可见，在样例环境下，牧场 $10$ 到所有贝茜喜欢的牧场的平均距离最小，为最佳牧场。
输入格式
第一行包含三个整数 $P$,$F$,$C$。
接下来 $F$ 行，每行一个整数，表示贝茜喜欢的牧场的编号。
接下来 $C$ 行，每行三个整数 $a_i$,$b_i$,$T_i$，表示存在一条连接 $a_i$ 和 $b_i$ 的双向通路，通过时间为 $T_i$。
输出格式
一个整数，表示最佳的牧场编号。如果有多个最佳牧场，则输出编号最小的那一个。
说明/提示
翻译来自 AASDFGHJKL(1035916)。