Editorial for DMOPC '17 Contest 1 P3 - Hitchhiking Fun

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For the first subtask, since all roads are dangerous, it suffices to run a Breadth-First Search, and then print the shortest distance from node $1$ ~1~ to node $N$ ~N~.

Time Complexity: $\mathcal O(N + M)$ ~\mathcal O(N + M)~

For the second subtask, we can remove the single dangerous road, and then run a Breadth-First Search. If there exists a path from node $1$ ~1~ to node $N$ ~N~, then the minimum number of dangerous roads needed is $0$ ~0~. Otherwise, we know that if there exists a path from $1$ ~1~ to $N$ ~N~, it must pass through the single dangerous path. Thus we can run a Breadth-First Search, and print the shortest distance from $1$ ~1~ to $N$ ~N~.

Time Complexity: $\mathcal O(N + M)$ ~\mathcal O(N + M)~

For the final subtask, we notice that we can perform a modified single source shortest path, by first comparing the danger value, and breaking ties with the distance.

Time Complexity: $\mathcal O(M \log N)$ ~\mathcal O(M \log N)~

Comments

3

vmaddur commented on Oct. 12, 2017, 3:30 p.m.

Kirito Could a 0-1 BFS work, even though we have to account for total number of roads traveled?