Approach 1: Dijkstra's
Treating the original graph as a weighted, undirected graph, we can use Dijkstra's algorithm to find all reachable nodes in the original graph. However, this won't be enough to solve examples where subdivided edges are only used partially.
When we travel along an edge (in either direction), we can keep track of how much we use it. At the end, we want to know every node we reached in the original graph, plus the sum of the utilization of each edge.
We use Dijkstra's algorithm to find the shortest distance from our source to all targets. This is a textbook algorithm, refer to this link for more details.
Additionally, for each (directed) edge
(node, nei), we'll keep track of how many "new" nodes (new from subdivision of the original edge) were
used. At the end, we'll sum up the utilization of each edge.
Please see the inline comments for more details.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.