#882
Reachable Nodes In Subdivided Graph
candidate master · 1400 · lc hard +32 · verified · 51.8% accepted · 899 likes · top 41%
Description
You have an undirected graph of n nodes (labeled 0 to n - 1). Each edge is subdivided into a chain by inserting new nodes between the endpoints.
The graph is given as edges where edges[i] = [ui, vi, cnti] means there is an original edge between ui and vi, and cnti new nodes are inserted along it (so the edge becomes cnti + 1 smaller edges). If cnti == 0, the edge is not subdivided.
From node 0, a node in the new graph is reachable if the shortest path from 0 to it has length at most maxMoves.
Return the total number of nodes (original and newly inserted) reachable from node 0.
Example 1:
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
Explanation: The edge subdivisions are shown in the image above.
The nodes that are reachable are highlighted in yellow.
Example 2:
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23
Example 3:
Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
Output: 1
Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.
Code
1
2
3