网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
最佳地点
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | bestspot.in | 输出文件 | bestspot.out |
最佳地点
贝茜总是希望优化她的人生,她很想访问约翰农场所拥有的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