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 to node .

Time Complexity:

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 to node , then the minimum number of dangerous roads needed is . Otherwise, we know that if there exists a path from to , it must pass through the single dangerous path. Thus we can run a Breadth-First Search, and print the shortest distance from to .

Time Complexity:

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: