题目名称 522. 最佳地点
输入输出 bestspot.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2010-12-24加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:15, 提交:21, 通过率:71.43%
Gravatar郭乾乐 100 0.250 s 1.21 MiB C++
Gravatar了反取字名我擦 100 0.269 s 1.22 MiB C++
GravatarPom 100 0.288 s 1.22 MiB C++
Gravatar苏轼 100 0.292 s 0.26 MiB C++
Gravatar王者自由 100 0.342 s 1.21 MiB C++
Gravatarkaaala 100 0.363 s 1.21 MiB C++
Gravatar苏轼 100 0.397 s 1.22 MiB C++
Gravatarmagic 100 0.501 s 1.22 MiB C++
Gravatarnick09 100 0.778 s 1.07 MiB Pascal
Gravatarwo shi 刘畅 100 0.782 s 1.07 MiB Pascal
本题关联比赛
20101224
关于 最佳地点 的近10条评论(全部评论)

522. 最佳地点

★   输入文件:bestspot.in   输出文件:bestspot.out   简单对比
时间限制:1 s   内存限制:128 MiB


最佳地点

贝茜总是希望优化她的人生,她很想访问约翰农场所拥有的P(1 <= F <= P)个草地中的F(1 <= P <= 500; 1 <= F_i <= P)个。
贝茜知道,她只能在C (1 <= C <= 8,000)条双向的路径上旅行,在路径P_i旅行,需要时间T_i(1 <= T_i <= 892),路径的两个端点是a_i and b_i (1 <= a_i <=P; 1 <= b_i <= P).
贝茜想找一个最好的草地睡觉,并且到达这个草地能让这次旅行的平均时间最短。
例如,下面是一个农场的草地分布图,带*号的草地是贝茜特别喜欢的,括号中的数是该路径的旅行时间。
 

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

如此可知,最好草地是10号草地



输入格式

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

* 第2..F+1行: 每行表示一个整数: F_i

* 第F+2..C+F+1行: 行 i+F+1 描述路径i,用三个空格隔开的整数: a_i, b_i, and T_i

输入样例 (file bestspot.in):

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

输出格式:

* 只有一行一个整数,表示最好的草地,如果有多解,输出最小的.

输出样例 (file bestspot.out):

10