1634--【USACO】Best Spot(最好的地方)

1634: 【USACO】Best Spot(最好的地方)


时间限制: 1.000 Sec  内存限制: 256 MB
提交: 49  解决: 27
[提交] [状态] [报告] [命题人:]

题目描述

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.
            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:
                       * * * * * * 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.


贝茜总是希望优化她的生活,她意识到她真的很喜欢去参观F(1<=F<=P)最喜欢的牧场F_i(1<=P<=500;1<=F_i<=P),总牧场(方便地编号为1.P)构成了农民约翰的财产。贝茜知道,她可以在C(1<=C<=8000)双向牛仔路径(方便编号1..C)中导航,将各种牧场连接到整个农场的任何牧场。与每条路径P_i相关联的是一个时间T_i(1<=T_i<=892)来遍历该路径(任意方向)和两个路径端点a_i和b_i(1<=a_i<=P;1<=b_i<=P)。贝茜想找出最好的牧场的数量,以便当她醒来时,去她最喜欢的牧场的平均时间被减少。举个例子,考虑一个农场,如下面的地图所示,其中*d牧场编号是最喜欢的。括号内的数字是穿越牛仔路的时间。

            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的潜在“最佳地点”的距离:

                       * * * * * * 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

因此,假设这些选择是最好的选择(程序必须检查所有这些选择),最好的睡眠地点是牧场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

*第1行:三个空格分隔的整数:P,F,和C

*行2.F1:第I2行包含一个整数:F_i*行F2.C1:I行F_1用三个空格分隔整数:a_i,b_i和T_i来描述路径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
输出  复制
10

提示

INPUT DETAILS: As the problem statement 
OUTPUT DETAILS: As the problem statement.

来源/分类