Construct a weighted directed graph on the $N$ towns, with a directed edge from town $u$ to town $v$ if $diff[u]>diff[v]$ and there is a road connecting $u$ and $v$, 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 $X$ to $Y$. We will never traverse a path where we will face obstacles because such roads were not included in the graph.

Complexity: $O(L(V\log(V) + E))$

**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: $O(L(V+E))$

Note that, such a path might not exist, even if $X$ and $Y$ are connected via roads.

58% Solution Ratio

jamil314Earliest,

Ahasan_1999Fastest, 0.2s

sakib.17442Lightest, 6.9 MB

Deshi_TouristShortest, 982B

Toph uses cookies. By continuing you agree to our Cookie Policy.