A facility has n rooms (numbered 0 to n-1) joined by two-way corridors. Each corridor is either already open (you may walk through it for free) or locked (you must spend one keycard charge to open and pass through it, in either direction).
Starting in room 0, you want to reach room n-1. Find the minimum total number of keycard charges spent (equivalently, the fewest locked corridors you must pass through). If room n-1 cannot be reached at all, report that it is impossible.
Line 1: two integers n and m (rooms and corridors).
Each of the next m lines: three integers u v w, a two-way corridor between rooms u and v, where w is 0 (open) or 1 (locked).
A single integer: the minimum number of keycard charges to get from room 0 to room n-1, or -1 if unreachable.
Example 1
Input
4 4 0 1 0 1 3 1 0 2 1 2 3 0
Expected
1
Explanation
0->1 is open (0), 1->3 is locked (1): total 1. The other route 0->2->3 also costs 1. The minimum is 1.
Example 2
Input
3 2 0 1 0 1 2 0
Expected
0
Explanation
Both corridors on 0->1->2 are open, so you reach room 2 without spending any charge: 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →