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.

Authors: 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 to node N.

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

Time Complexity: \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)


Comments


  • 1
    vmaddur  commented on Oct. 12, 2017, 11:30 a.m.

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