Press "Enter" to skip to content

花花酱 LeetCode 882. Reachable Nodes In Subdivided Graph


Starting with an undirected graph (the “original graph”) with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, ..., x_n) are added to the original graph,

and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.


Example 1:

Input: edge = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3 
Output: 13 
Explanation:  The nodes that are reachable in the final graph after M = 6 moves are indicated below. 

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4 
Output: 23


  1. 0 <= edges.length <= 10000
  2. 0 <= edges[i][0] < edges[i][1] < N
  3. There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].
  4. The original graph has no parallel edges.
  5. 0 <= edges[i][2] <= 10000
  6. 0 <= M <= 10^9
  7. 1 <= N <= 3000

Solution: Dijkstra Shortest Path

Compute the shortest from 0 to rest of the nodes. Use HP to mark the maximum moves left to reach each node.

HP[u] = a, HP[v] = b, new_nodes[u][v] = c

nodes covered between a<->b = min(c, a + b)

Time complexity: O(ElogE)

Space complexity: O(E)


Optimized Dijkstra (replace hashmap with vector)

Using SPFA




If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website


Be First to Comment

Leave a Reply