# LeetCode 882: Reachable Nodes In Subdivided Graph

## Problem Restatement

We are given an undirected graph with original nodes numbered from `0` to `n - 1`.

Each edge is written as:

```text
[u, v, cnt]
```

This means the original edge between `u` and `v` is subdivided by adding `cnt` new nodes between them.

For example:

```text
[0, 1, 3]
```

becomes:

```text
0 - x1 - x2 - x3 - 1
```

So moving from `0` to `1` through this edge takes `cnt + 1` moves.

Starting from node `0`, we can make at most `maxMoves` moves.

Return how many nodes are reachable in the new subdivided graph. This includes both original nodes and new subdivided nodes. The problem defines a node as reachable if its distance from node `0` is at most `maxMoves`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `edges`, `maxMoves`, and `n` |
| Output | Number of reachable nodes in the subdivided graph |
| Original nodes | Numbered `0` through `n - 1` |
| Edge format | `[u, v, cnt]` |
| Subdivision rule | Add `cnt` new nodes between `u` and `v` |
| Start node | `0` |
| Reachability | Distance from `0` is at most `maxMoves` |

Function shape:

```python
def reachableNodes(
    self,
    edges: list[list[int]],
    maxMoves: int,
    n: int
) -> int:
    ...
```

## Examples

Example 1:

```text
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
```

The edge `[0,1,10]` has 10 new nodes.

The edge `[0,2,1]` has 1 new node.

The edge `[1,2,2]` has 2 new nodes.

We count every original node reachable from `0`, and every subdivided node reachable along each edge.

Example 2:

```text
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23
```

The shortest distances between original nodes use edge weights `cnt + 1`.

For example, edge `[0,1,4]` takes `5` moves to cross.

With `10` moves, all four original nodes are reachable, and all subdivided nodes on the edges are reachable, so the answer is `23`.

## First Thought: Build the Full Graph

A direct idea is to explicitly create every new node.

For edge:

```text
[u, v, cnt]
```

we create nodes:

```text
x1, x2, ..., xcnt
```

and edges:

```text
u - x1 - x2 - ... - xcnt - v
```

Then we can run BFS or Dijkstra from node `0` and count nodes with distance at most `maxMoves`.

This is logically simple, but it can create too many nodes.

If many edges have large `cnt`, the expanded graph becomes much larger than the input graph.

## Key Insight

We do not need to build the subdivided graph.

Each original edge `[u, v, cnt]` behaves like a weighted edge of cost:

```text
cnt + 1
```

between original nodes `u` and `v`.

So first, compute shortest distances from node `0` to every original node using Dijkstra.

Then count:

1. Original nodes whose shortest distance is at most `maxMoves`.
2. Subdivided nodes reachable from either side of each original edge.

For an edge `[u, v, cnt]`, suppose:

```text
dist[u] = shortest distance from 0 to u
dist[v] = shortest distance from 0 to v
```

From the `u` side, we can enter at most:

```python
max(0, maxMoves - dist[u])
```

subdivided nodes.

From the `v` side, we can enter at most:

```python
max(0, maxMoves - dist[v])
```

subdivided nodes.

But the edge only has `cnt` subdivided nodes, so the number reachable on this edge is:

```python
min(
    cnt,
    max(0, maxMoves - dist[u]) + max(0, maxMoves - dist[v])
)
```

This avoids double counting overlap from both sides.

## Algorithm

Build a weighted adjacency list using only the original nodes.

For each edge `[u, v, cnt]`, add:

```text
u -> v with weight cnt + 1
v -> u with weight cnt + 1
```

Run Dijkstra from node `0`.

Then initialize:

```python
answer = number of original nodes with dist[node] <= maxMoves
```

For each original edge `[u, v, cnt]`:

1. Compute how many subdivided nodes are reachable from `u`.
2. Compute how many subdivided nodes are reachable from `v`.
3. Add the capped total:

```python
answer += min(cnt, from_u + from_v)
```

Return `answer`.

## Walkthrough

Use:

```text
edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]]
maxMoves = 10
n = 4
```

Convert each subdivided edge into a weighted edge:

| Edge | Subdivided nodes | Weighted cost |
|---|---:|---:|
| `[0,1,4]` | 4 | 5 |
| `[1,2,6]` | 6 | 7 |
| `[0,2,8]` | 8 | 9 |
| `[1,3,1]` | 1 | 2 |

Dijkstra gives:

| Original node | Distance from `0` |
|---|---:|
| `0` | 0 |
| `1` | 5 |
| `2` | 9 |
| `3` | 7 |

All 4 original nodes are reachable.

Now count subdivided nodes:

| Edge | From first side | From second side | Counted |
|---|---:|---:|---:|
| `[0,1,4]` | `10 - 0 = 10` | `10 - 5 = 5` | `min(4, 15) = 4` |
| `[1,2,6]` | `10 - 5 = 5` | `10 - 9 = 1` | `min(6, 6) = 6` |
| `[0,2,8]` | `10 - 0 = 10` | `10 - 9 = 1` | `min(8, 11) = 8` |
| `[1,3,1]` | `10 - 5 = 5` | `10 - 7 = 3` | `min(1, 8) = 1` |

Total:

```text
original nodes: 4
subdivided nodes: 4 + 6 + 8 + 1 = 19
answer: 23
```

## Correctness

Dijkstra computes the shortest distance from node `0` to every original node because all weighted edge costs are positive. Each original edge `[u, v, cnt]` has traversal cost `cnt + 1`, which exactly matches the number of moves needed to go from `u` to `v` through all subdivided nodes.

An original node is reachable exactly when its shortest distance is at most `maxMoves`, so counting such nodes is correct.

Now consider one original edge `[u, v, cnt]`.

If `u` is reachable with `dist[u]` moves, then after reaching `u`, we have `maxMoves - dist[u]` moves left. Each remaining move can advance one subdivided node along the edge from the `u` side. Therefore, the number reachable from the `u` side is `max(0, maxMoves - dist[u])`, capped by `cnt`.

The same reasoning applies from the `v` side.

Some subdivided nodes may be reachable from both sides. Since the edge contains only `cnt` subdivided nodes, the number of distinct reachable subdivided nodes on this edge is the smaller of `cnt` and the sum of the reachable counts from both sides.

Each subdivided node belongs to exactly one original edge, so summing this value over all edges counts every reachable subdivided node exactly once.

Therefore, the algorithm returns the exact number of reachable nodes in the subdivided graph.

## Complexity

Let:

```text
V = n
E = len(edges)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(E log V)` | Dijkstra with a heap, plus one scan over edges |
| Space | `O(V + E)` | Adjacency list, distance array, and heap |

## Implementation

```python
import heapq
from collections import defaultdict

class Solution:
    def reachableNodes(
        self,
        edges: list[list[int]],
        maxMoves: int,
        n: int
    ) -> int:
        graph = defaultdict(list)

        for u, v, cnt in edges:
            weight = cnt + 1
            graph[u].append((v, weight))
            graph[v].append((u, weight))

        dist = [float("inf")] * n
        dist[0] = 0

        heap = [(0, 0)]

        while heap:
            curr_dist, node = heapq.heappop(heap)

            if curr_dist > dist[node]:
                continue

            for nei, weight in graph[node]:
                next_dist = curr_dist + weight

                if next_dist < dist[nei]:
                    dist[nei] = next_dist
                    heapq.heappush(heap, (next_dist, nei))

        answer = 0

        for d in dist:
            if d <= maxMoves:
                answer += 1

        for u, v, cnt in edges:
            from_u = 0
            if dist[u] <= maxMoves:
                from_u = maxMoves - dist[u]

            from_v = 0
            if dist[v] <= maxMoves:
                from_v = maxMoves - dist[v]

            answer += min(cnt, from_u + from_v)

        return answer
```

## Code Explanation

We build the graph over original nodes only:

```python
for u, v, cnt in edges:
    weight = cnt + 1
    graph[u].append((v, weight))
    graph[v].append((u, weight))
```

The weight is `cnt + 1` because crossing the whole subdivided edge requires passing through `cnt` new nodes and then reaching the other original node.

The distance array stores shortest distances from node `0`:

```python
dist = [float("inf")] * n
dist[0] = 0
```

Dijkstra processes the currently closest known original node:

```python
curr_dist, node = heapq.heappop(heap)
```

If the heap entry is outdated, we skip it:

```python
if curr_dist > dist[node]:
    continue
```

Then we relax each neighboring original node:

```python
next_dist = curr_dist + weight

if next_dist < dist[nei]:
    dist[nei] = next_dist
    heapq.heappush(heap, (next_dist, nei))
```

After shortest distances are known, we count reachable original nodes:

```python
for d in dist:
    if d <= maxMoves:
        answer += 1
```

Then we count reachable subdivided nodes on each edge:

```python
answer += min(cnt, from_u + from_v)
```

The `min` prevents counting more subdivided nodes than the edge actually contains.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.reachableNodes(
        [[0, 1, 10], [0, 2, 1], [1, 2, 2]],
        6,
        3
    ) == 13

    assert s.reachableNodes(
        [[0, 1, 4], [1, 2, 6], [0, 2, 8], [1, 3, 1]],
        10,
        4
    ) == 23

    assert s.reachableNodes(
        [[1, 2, 4], [1, 4, 5], [1, 3, 1], [2, 3, 4], [3, 4, 5]],
        17,
        5
    ) == 1

    assert s.reachableNodes(
        [],
        5,
        1
    ) == 1

    assert s.reachableNodes(
        [[0, 1, 0]],
        1,
        2
    ) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| First official-style example | Counts original and subdivided nodes |
| Larger connected example | Checks Dijkstra and edge counting |
| Node `0` disconnected | Only node `0` is reachable |
| No edges | Single original node only |
| Edge with `cnt = 0` | Original edge without subdivision |