> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.
> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.
# Reachable Nodes In Subdivided Graph
> Tested Python solution for LeetCode 882 with 22 pytest cases. Generate a practice environment with lcpy.
LeetCode 882, [Hard](/catalog/hard). Topics: [Graph Theory](/catalog/topics/graph-theory), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Shortest Path](/catalog/topics/shortest-path), Dijkstra's Algorithm. [View on LeetCode](https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/description/).
Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:
```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 882 # by problem number
lcpy gen -s reachable_nodes_in_subdivided_graph # by problem name
```
## Problem
You are given an undirected graph (the **"original graph"**) with `n` nodes labeled from `0` to `n - 1`. You decide to **subdivide** each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.
The graph is given as a 2D array of `edges` where `edges[i] = [ui, vi, cnti]` indicates that there is an edge between nodes `ui` and `vi` in the original graph, and `cnti` is the total number of new nodes that you will **subdivide** the edge into. Note that `cnti == 0` means you will not subdivide the edge.
To **subdivide** the edge `[ui, vi]`, replace it with `(cnti + 1)` new edges and `cnti` new nodes. The new nodes are `x1`, `x2`, ..., `xcnti`, and the new edges are `[ui, x1]`, `[x1, x2]`, `[x2, x3]`, ..., `[xcnti-1, xcnti]`, `[xcnti, vi]`.
In this **new graph**, you want to know how many nodes are **reachable** from the node `0`, where a node is **reachable** if the distance is `maxMoves` or less.
Given the original graph and `maxMoves`, return *the number of nodes that are **reachable** from node *`0`* in the new graph*.
### Examples
```
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.
```
```
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23
```
```
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.
```
### Constraints
* 0 \<= edges.length \<= min(n \* (n - 1) / 2, 10\4\)
* edges\[i].length == 3
* 0 \<= u\i\ \< v\i\ \< n
* There are no multiple edges in the graph.
* 0 \<= cnt\i\ \<= 10\4\
* 0 \<= maxMoves \<= 10\9\
* 1 \<= n \<= 3000
## Solution
Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reachable_nodes_in_subdivided_graph/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reachable_nodes_in_subdivided_graph/test_solution.py):
```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq
class Solution:
# Time: O(E log V)
# Space: O(V + E)
def reachable_nodes(self, edges: list[list[int]], max_moves: int, n: int) -> int:
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for u, v, cnt in edges:
adj[u].append((v, cnt))
adj[v].append((u, cnt))
unreachable = max_moves + 1
dist = [unreachable] * n
dist[0] = 0
heap: list[tuple[int, int]] = [(0, 0)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue
for nxt, cnt in adj[node]:
nd = d + cnt + 1
if nd < dist[nxt]:
dist[nxt] = nd
heapq.heappush(heap, (nd, nxt))
reachable = sum(1 for d in dist if d <= max_moves)
for u, v, cnt in edges:
head = max(0, max_moves - dist[u])
tail = max(0, max_moves - dist[v])
reachable += min(cnt, head + tail)
return reachable
```
## Complexity
| Time | Space |
| - | - |
| O(E log V) | O(V + E) |
## Tags
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.