Editorial for The Need for Seed

Construct a weighted directed graph on the NN towns, with a directed edge from town uu to town vv if diff[u]>diff[v]diff[u]>diff[v] and there is a road connecting uu and vv, 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 XX to YY. We will never traverse a path where we will face obstacles because such roads were not included in the graph.
Complexity: O(L(Vlog(V)+E))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))O(L(V+E))

Note that, such a path might not exist, even if XX and YY are connected via roads.


    58% Solution Ratio

    jamil314Earliest, 3M ago

    Ahasan_1999Fastest, 0.2s

    sakib.17442Lightest, 6.9 MB

    Deshi_TouristShortest, 982B

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