## Editorial for DMOPC '17 Contest 1 P3 - Hitchhiking Fun

**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:

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:**

## Comments

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