## RGPC '17 P4 - Snow Day

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

One morning, you wake up to find that it snowed hard overnight, and that school buses have now been cancelled. To celebrate, you decide to go tobogganing at the giant hill in your neighbourhood. At the top of the hill, you see that there are several possible paths down the hill, and that each path may split, merge, or intersect with others at "scenic points". More specifically, there are scenic points numbered from to , and paths from point to point that have a length of .

You want to take the longest path down (from point to point ), but would also like to stop at the greatest number of scenic points, while prioritizing the longest path. What would be the greatest distance that you can slide, as well as the number of scenic points that you would stop at on that particular route?

#### Input Specification

The first line of input will contain and , space-separated integers. The next lines will each contain 3 space-separated integers , , and , representing a path from point to point with a length of .

Note: paths are not bidirectional. It would not be possible to slide up a hill.

#### Output Specification

Output the total distance of the longest route possible and the number of scenic points on that route, separated by a space. Output if it is not possible to reach the bottom of the hill, or if any paths form a cycle.

#### Sample Input 1

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

#### Sample Output 1

5 4

#### Explanation for Sample Output 1

Path has a length of 5, and visits 4 scenic points.
Path has a length of 4, and visits 4 scenic points.
Path has a length of 4, and visits 3 scenic points.

Therefore, the path that should be chosen is the first one, as it is the longest.

#### Sample Input 2

5 5
1 2 1
2 3 2
2 4 3
3 1 2
4 5 1

#### Sample Output 2

-1

#### Explanation for Sample Output 2

There is a cycle (). Since you can't go down a hill and end up at the top, this is an impossible scenario.

• commented on Aug. 25, 2019, 1:31 a.m.

For the first test case, shouldn't only nodes 1, 2, and 6 be scenic points?

• commented on June 11, 2017, 9:31 p.m. edit 2

Is it possible that a 32-bit integer is not sufficient enough to store the distances? Please specify.

• commented on June 11, 2017, 10:46 p.m.

Why not try calculating the worst-case distance yourself? From the constraints, we see that is at most and that is at most . If each path was of maximum length, then the greatest total distance would be ( paths of length ). However, this isn't logical, because there aren't that many scenic points, so revisiting one would create a cycle. Thus, the greatest total distance (a line from point to point ) would be , which is less than .

Problems that don't specify whether or not you need 64-bit variables will often give you important constraints, allowing you to determine that yourself. Just putting this here for anyone who doesn't know how to do this. Correct me if I'm wrong anywhere.