Construct a weighted directed graph on the towns, with a directed edge from town to town if and there is a road connecting and , weighting the edge by the time taken to cross the road.
For Subtask #1
You can run Djikstra’s Algorithm to find the shortest path from to . We will never traverse a path where we will face obstacles because such roads were not included in the graph.
Complexity:
For Subtask #2
This graph is acyclic because the total order specified by difficulty represents a topologically sorted order. Find the topological order of the nodes using DFS. Then relax the outgoing edges in the found topological order to find the shortest path.
Complexity:
Note that, such a path might not exist, even if and are connected via roads.