Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Sightseeing Cows
Description Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time. Fortunately, they have a detailed city map showing the While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values F ≤ 1000) for each landmark _{i}i.The cows also know about the cowpaths. Cowpath T ≤ 1000) to traverse._{i}In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off. Help the cows find the maximum fun value per unit time that they can achieve. Input * Line 1: Two space-separated integers: * Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L_{1i} , L_{2i} , and T _{i}Output * Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules. Sample Input 5 7 30 10 10 5 10 1 2 3 2 3 2 3 4 5 3 5 2 4 5 5 5 1 3 5 2 2 Sample Output 6.00 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator