72 - ZOJ Monthly, November 2008 - H
One day, you attend a treasure hunt game. You should start from one city, and go to some cities in order to collect treasures. You are given a map, which shows the number of treasures each city has. We assume if you go to one city, you can get all treasures in it.
For the sake of saving time, you do not want to go to one city more than once, except the start city, because you are asked to go back to the start city finally. Furthermore, it cost you some time to go to another city from one city.
Let SUM be the number of treasures you finally get, also, let TIME be the total cost time. Your task is not to collect as many as possible but to maximize SUM / TIME.
You can start at any city you like, and go back to this city at last. Also, you should go to at least two cities.
The first line contains two integers, N and M, which represents the number of cities and roads (N <= 300, M <= 2000). Then N numbers, which shows the number of treasures the i-th city has. The last M lines in format of "city X city Y TIME", means the time going from city X to city Y costs. The roads are directed.
Output the SUM and TIME of the best strategy, which makes SUM / TIME largest. You can assume that the answer is unique.
5 7 1 4 3 5 10 1 2 3 2 3 4 3 4 5 3 5 7 4 5 5 5 1 6 5 2 2
The route is 2 -> 3 -> 4 -> 5 -> 2.
Author: LIN, Yue