RGPC '17 P4 - Snow Day

View as PDF

Submit solution

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

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 N scenic points numbered from 1 to N, and M paths from point a_i to point b_i that have a length of d_i.

You want to take the longest path down (from point 1 to point N), 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 N and M, space-separated integers. The next M lines will each contain 3 space-separated integers a_i, b_i, and d_i, representing a path from point a_i to point b_i with a length of d_i.

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


For all subtasks:

1 \le a_i < N

1 < b_i \le N

a_i \ne b_i

Subtask 1 [10%]

1 < N \le 100

1 \le M \le 1\,000

d_i = 1

Subtask 2 [90%]

1 < N \le 1\,000

1 \le M \le 100\,000

1 \le d_i \le 1\,000\,000

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 -1 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 1 \to 2 \to 4 \to 6 has a length of 5, and visits 4 scenic points.
Path 1 \to 2 \to 5 \to 6 has a length of 4, and visits 4 scenic points.
Path 1 \to 3 \to 6 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


Explanation for Sample Output 2

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


  • 0
    Arman_Lamei  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?

  • -1
    Ninjaclasher  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.

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

      Why not try calculating the worst-case distance yourself? From the constraints, we see that d_i is at most 1\,000\,000 and that M is at most 100\,000. If each path was of maximum length, then the greatest total distance would be d_i \times M (M paths of length 1\,000\,000). 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 1 to point N) would be d_i \times (N - 1) = 999\,000\,000, which is less than 2^{31} - 1.

      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.