1070. Reachable Nodes in Subdivided Graph

Given an undirected graph on n nodes where each edge [u, v, cnt] is subdivided into cnt intermediate new nodes (so the edge becomes a chain of cnt+1 segments), and a budget maxMoves, return how many nodes (original plus subdivided) are reachable from node 0 within maxMoves moves. The input is JSON {edges, maxMoves, n}.

Input: JSON {edges, maxMoves, n} with edges [u, v, cnt].

Output: Integer — the number of reachable nodes.

Examples

Input: {"edges":[[0,1,10],[0,2,1],[1,2,2]],"maxMoves":6,"n":3}
Output: 13
Explanation: Original plus reachable subdivided nodes.

Input: {"edges":[[0,1,4],[1,2,6],[0,2,8],[1,3,1]],"maxMoves":10,"n":4}
Output: 23
Explanation: Counted across all edges.

Input: {"edges":[[0,1,1]],"maxMoves":0,"n":2}
Output: 1
Explanation: Only the start node.

Constraints

• 1<=n<=3000
• 0<=cnt<=10^4

Asked by