RGPC '17 P4 - Snow Day - DMOJ: Modern Online Judge

RGPC '17 P4 - Snow Day

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

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

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

Constraints

For all subtasks:

$1 \le a_i < N$ $1 \leq a_{i} < N$

$1 < b_i \le N$ $1 < b_{i} \leq N$

$a_i \ne b_i$ $a_{i} \neq b_{i}$

Subtask 1 [10%]

$1 < N \le 100$ $1 < N \leq 100$

$1 \le M \le 1\,000$ $1 \leq M \leq 1 000$

$d_i = 1$ $d_{i} = 1$

Subtask 2 [90%]

$1 < N \le 1\,000$ $1 < N \leq 1 000$

$1 \le M \le 100\,000$ $1 \leq M \leq 100 000$

$1 \le d_i \le 1\,000\,000$ $1 \leq d_{i} \leq 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$ $- 1$ if it is not possible to reach the bottom of the hill, or if any paths form a cycle.

Sample Input 1

Copy

Sample Output 1

Copy

5 4

Explanation for Sample Output 1

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

Copy

Sample Output 2

Copy

-1

Explanation for Sample Output 2

There is a cycle ( $1 \to 2 \to 3 \to 1$ $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.

Comments

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$ $d_{i}$ is at most $1\,000\,000$ $1 000 000$ and that $M$ $M$ is at most $100\,000$ $100 000$ . If each path was of maximum length, then the greatest total distance would be $d_i \times M$ $d_{i} \times M$ ( $M$ $M$ paths of length $1\,000\,000$ $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$ $1$ to point $N$ $N$ ) would be $d_i \times (N - 1) = 999\,000\,000$ $d_{i} \times (N - 1) = 999 000 000$ , which is less than $2^{31} - 1$ $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.