DMOPC '17 Contest 1 P3 - Hitchhiking Fun

View as PDF

Submit solution



Points:7 (partial)
Time limit:2.0s
Memory limit:64M
Author:

Problem type

Bob is hitchhiking from city to city. There are N cities numbered from 1 to N and M bidirectional roads. He starts at city 1 and wants to get to city N. He has researched each road, and designated each one as either safe or dangerous for hitchhikers. Assuming that Bob will always be able to find a ride, find the minimum number of dangerous roads Bob must travel along to get to city N. Bob also wants to know the minimum number of roads he must travel on while still minimizing the number of dangerous roads.

Constraints

Subtask 1 [20%]

All roads are dangerous.
1\leq N, M\leq 10^5

Subtask 2 [20%]

Exactly one road is dangerous.
1\leq N, M\leq 10^5

Subtask 3 [20%]

1\leq N\leq 10^3
1\leq M\leq 10^5

Subtask 4 [40%]

1\leq N, M\leq 10^5

Input Specification

The first line contains two integers representing N and M.

The following M lines contain three space-separated integers each. The i^{\text{th}} line contains a_i, b_i, and t_i, indicating a road from city a_i to city b_i. If t_i is 0, then this road is safe. Otherwise, t_i is 1 and this road is dangerous.

Output Specification

If Bob cannot reach city N at all, output -1. Otherwise, output two space-separated integers: the minimum number of dangerous roads and the minimum number of roads while minimizing the number of dangerous roads.

Sample Input 1

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

Sample Output 1

0 3

Explanation for Sample 1

Although Bob can go directly from city 1 to city 4, this path goes along a dangerous road. He can completely avoid dangerous roads by going from city 1 to city 2 to city 3 and finally to city 4.

Sample Input 2

4 6
1 1 0
1 3 1
4 2 1
4 3 0
2 4 0
2 3 0

Sample Output 2

1 2

Sample Input 3

4 3
1 2 1
2 3 1
1 3 0

Sample Output 3

-1

Comments

There are no comments at the moment.