AIOC Banner

Problem: Happy Feet

Want to try solving this problem? You can submit your code online if you log in or register.

Happy Feet

Input File: standard input
Output File: standard output
Time Limit: 0.5 seconds
Memory Limit: 64 MB

Forget space flights, undersea submarine voyages and desert treks. Today's frontier of tourism is watching the famous dancing penguins of Antarctica. As the founder of a new company selling hiking tours in the southern-most continent, your killer whale of a business plan is to find the perfect hiking tour of the penguin colonies that will be most enjoyable for the wealthy tourists.

After lengthy discussions with Antarctican penguin experts, you have developed a map of all the human-walkable trails in the region. Each trail leads from one intersection to another intersection and can be walked in either direction. Note that a trail may lead from an intersection back to itself, and there may be multiple trails between two intersections. The experts have given you accurate figures of how many penguins will be seen dancing on each trail. You would like to find a path with the highest total number of penguins seen along the way. This path can start at any intersection and finish at any intersection (including the starting intersection). It may even involve visiting the same intersection multiple times. The only condition is that each trail in the path must have strictly more penguins than any previous trail. Tourists exhibit a strange psychological complex requiring their expectations to be continually exceeded. Failure to do so would mean a catastrophic post-trip influx of negative travel reviews.

Given the trail map, write a program to find the largest total number of penguins that can be seen on such a path.



Output should consist of a single integer: the maximum possible number of penguins that can be seen on a path satisfying the described conditions.

Sample Input

5 9
1 2 4
2 3 2
1 3 1
1 4 3
4 3 4
4 3 5
3 5 6
4 5 6
5 5 7

Sample Output



The optimal path in the sample case above takes the following trails, beginning at intersection 3 and ending at intersection 5.

From To Penguins seen
3 1 1
1 4 3
4 3 4
3 4 5
4 5 6
5 5 7

This path has a total of 1+3+4+5+6+7=26 penguins. No valid path exists with more penguins, hence 26 is the correct answer.

Subtasks & Constraints

In all subtasks, 1 ≤ N ≤ 1,000 and each trail will have between 1 and 1,000,000 penguins (inclusive).

You will score the full allocated marks for a subtask if your program returns the correct answer for every test case within that subtask. If your program fails any test case in a subtask, your score will be 0 for that subtask.


Privacy statement
© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021,  9:27am AEST