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

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.

- The first line of input will contain two integers N and M,
representing the number of intersections and number of trails respectively.
- The following M lines of input will each contain three integers a
_{i}, b_{i}, and p_{i}representing a trail. The trail connects intersections a_{i}and b_{i}and has p_{i}penguins that can be seen dancing on it. Intersections are labelled 1..N, that is, 1 ≤ a_{i}, b_{i}≤ N.

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

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

26

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.

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

- Subtask 1 (30 points): 1 ≤ M ≤ 1,000.
- Subtask 2 (40 points): 1 ≤ M ≤ 1,000,000 and it is guaranteed
that no two trails will have the same number of penguins on them (that is, all
trail penguin counts will be unique).
- Subtask 3 (30 points): 1 ≤ M ≤ 1,000,000.

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