DMOPC '17 Contest 1 P3 - Hitchhiking Fun

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.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.
1N,M105

Subtask 2 [20%]

Exactly one road is dangerous.
1N,M105

Subtask 3 [20%]

1N103
1M105

Subtask 4 [40%]

1N,M105

Input Specification

The first line contains two integers representing N and M.

The following M lines contain three space-separated integers each. The ith line contains ai, bi, and ti, indicating a road from city ai to city bi. If ti is 0, then this road is safe. Otherwise, ti 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

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

Sample Output 1

Copy
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

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

Sample Output 2

Copy
1 2

Sample Input 3

Copy
4 3
1 2 1
2 3 1
1 3 0

Sample Output 3

Copy
-1

Comments

There are no comments at the moment.