Reachable Waypoints in a Subdivided Network Within a Budget
Each network link is subdivided into a chain of intermediate waypoints. Starting from node 0 with a movement budget, count how many nodes and intermediate waypoints you can reach.
Problem
An undirected graph has n nodes (0..n-1). Each edge [u, v, cnt] is subdivided into cnt new intermediate nodes (so the edge becomes a path of cnt+1 sub-edges). Given maxMoves, return how many original nodes and subdivided nodes are reachable from node 0 using at most maxMoves moves (each sub-edge is one move).
Input
An edges list of [u, v, cnt], an integer maxMoves, and an integer n.
Output
An integer: the count of reachable nodes (original plus subdivided).
Constraints
- 0 <= edges.length <= min(n*(n-1)/2, 10^4)
- 0 <= cnt <= 10^4, 0 <= maxMoves <= 10^9, 1 <= n <= 3000
- There are no parallel edges or self-loops in the original graph.
Examples
Example 1
Input
edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output
13
All 3 original nodes plus 10 subdivided nodes are reachable within 6 moves.
Example 2
Input
edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output
23
The four originals plus reachable subdivisions sum to 23.