HBC24819比大小,语言题[USACO 2009 Jan S]Best Spot题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1

Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures Fi of the P (1 <= P <= 500; 1 <= Fi <= 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 Pi is a time Ti (1 <= Ti <= 892) to traverse that path (in either direction) and two path endpoints ai and bi (1 <= ai <= P; 1 <= bi <= 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.

想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。

标签： HBC24819比大小 语言题[USACO 2009 Jan S]Best Spot题解