# 882. Reachable Nodes In Subdivided Graph

### 題目敘述

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.

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.
``````

Constraints:

• `0 <= edges.length <= min(n * (n - 1) / 2, 104)`
• `edges[i].length == 3`
• `0 <= ui < vi < n`
• There are no multiple edges in the graph.
• `0 <= cnti <= 104`
• `0 <= maxMoves <= 109`
• `1 <= n <= 3000`

### 解法解析

#### 程式範例

##### JavaScript
``````/**
* @param {number[][]} edges
* @param {number} maxMoves
* @param {number} n
* @return {number}
*/
var reachableNodes = function (edges, maxMoves, n) {
const graph = {};
for (let [u, v, w] of edges) {
if (!(u in graph)) graph[u] = {};
if (!(v in graph)) graph[v] = {};
graph[u][v] = graph[v][u] = w;
}

const pq = new MinPriorityQueue({ priority: (x) => x[0] });
pq.enqueue([0, 0]);
const dist = { 0: 0 };
const used = {};
let ans = 0;

while (pq.size()) {
const [d, node] = pq.dequeue().element;
if (d > dist[node]) continue;
ans += 1;

for (const nei in graph[node]) {
const weight = graph[node][nei];
const v = Math.min(weight, maxMoves - d);
used[`\${node},\${nei}`] = v;

const d2 = d + weight + 1;
if (d2 < (dist?.[nei] ?? maxMoves + 1)) {
pq.enqueue([d2, nei]);
dist[nei] = d2;
}
}
}

for (const [u, v, w] of edges) {
ans += Math.min(
w,
(used?.[`\${u},\${v}`] ?? 0) + (used?.[`\${v},\${u}`] ?? 0)
);
}
return ans;
};
``````
##### Python
``````class Solution:
def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
graph = collections.defaultdict(dict)
for u, v, w in edges:
graph[u][v] = graph[v][u] = w

pq = [(0, 0)]
dist = {0: 0}
used = {}
ans = 0

while pq:
d, node = heapq.heappop(pq)
if d > dist[node]:
continue
# Each node is only visited once.  We've reached
# a node in our original graph.
ans += 1

for nei, weight in graph[node].items():
# maxMoves - d is how much further we can walk from this node;
# weight is how many new nodes there are on this edge.
# v is the maximum utilization of this edge.
v = min(weight, maxMoves - d)
used[node, nei] = v

# d2 is the total distance to reach 'nei' (neighbor) node
# in the original graph.
d2 = d + weight + 1
if d2 < dist.get(nei, maxMoves+1):
heapq.heappush(pq, (d2, nei))
dist[nei] = d2

# At the end, each edge (u, v, w) can be used with a maximum
# of w new nodes: a max of used[u, v] nodes from one side,
# and used[v, u] nodes from the other.
for u, v, w in edges:
ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

return ans
``````