Reachable Nodes In Subdivided Graph
Problem
Start at node 0 of an undirected graph; edge [u, v, cnt] is subdivided into cnt extra nodes forming a chain of length cnt + 1. With at most maxMoves moves (each move steps to an adjacent node), count how many nodes — original plus subdivided — are reachable. Run Dijkstra maximizing the moves remaining at each original node.
edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 313import heapq
def reachable_nodes(edges, max_moves, n):
adj = [dict() for _ in range(n)]
for u, v, cnt in edges:
adj[u][v] = adj[v][u] = cnt
heap = [(-max_moves, 0)]
seen, used, ans = {}, {}, 0
while heap:
moves, u = heapq.heappop(heap)
moves = -moves
if u in seen:
continue
seen[u] = moves
ans += 1
for v, cnt in adj[u].items():
used[(u, v)] = min(moves, cnt)
nxt = moves - cnt - 1
if v not in seen and nxt >= 0:
heapq.heappush(heap, (-nxt, v))
for u, v, cnt in edges:
ans += min(cnt, used.get((u, v), 0) + used.get((v, u), 0))
return ansfunction reachableNodes(edges, maxMoves, n) {
const adj = Array.from({ length: n }, () => new Map());
for (const [u, v, cnt] of edges) { adj[u].set(v, cnt); adj[v].set(u, cnt); }
const heap = [[maxMoves, 0]]; // by moves remaining (pop max each loop)
const seen = new Map(), used = new Map();
let ans = 0;
while (heap.length) {
heap.sort((a, b) => b[0] - a[0]);
const [moves, u] = heap.shift();
if (seen.has(u)) continue;
seen.set(u, moves); ans++;
for (const [v, cnt] of adj[u]) {
used.set(u + "," + v, Math.min(moves, cnt));
const nxt = moves - cnt - 1;
if (!seen.has(v) && nxt >= 0) heap.push([nxt, v]);
}
}
for (const [u, v, cnt] of edges) {
const a = used.get(u + "," + v) || 0, b = used.get(v + "," + u) || 0;
ans += Math.min(cnt, a + b);
}
return ans;
}int reachableNodes(int[][] edges, int maxMoves, int n) {
Map<Integer,Integer>[] adj = new HashMap[n];
for (int i = 0; i < n; i++) adj[i] = new HashMap<>();
for (int[] e : edges) { adj[e[0]].put(e[1], e[2]); adj[e[1]].put(e[0], e[2]); }
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
pq.add(new int[]{maxMoves, 0});
Map<Integer,Integer> seen = new HashMap<>();
Map<String,Integer> used = new HashMap<>();
int ans = 0;
while (!pq.isEmpty()) {
int[] top = pq.poll(); int moves = top[0], u = top[1];
if (seen.containsKey(u)) continue;
seen.put(u, moves); ans++;
for (var e : adj[u].entrySet()) {
int v = e.getKey(), cnt = e.getValue();
used.put(u + "," + v, Math.min(moves, cnt));
int nxt = moves - cnt - 1;
if (!seen.containsKey(v) && nxt >= 0) pq.add(new int[]{nxt, v});
}
}
for (int[] e : edges) {
int a = used.getOrDefault(e[0] + "," + e[1], 0);
int b = used.getOrDefault(e[1] + "," + e[0], 0);
ans += Math.min(e[2], a + b);
}
return ans;
}int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
vector<map<int,int>> adj(n);
for (auto& e : edges) { adj[e[0]][e[1]] = e[2]; adj[e[1]][e[0]] = e[2]; }
priority_queue<pair<int,int>> pq;
pq.push({maxMoves, 0});
map<int,int> seen;
map<pair<int,int>,int> used;
int ans = 0;
while (!pq.empty()) {
auto [moves, u] = pq.top(); pq.pop();
if (seen.count(u)) continue;
seen[u] = moves; ans++;
for (auto [v, cnt] : adj[u]) {
used[{u, v}] = min(moves, cnt);
int nxt = moves - cnt - 1;
if (!seen.count(v) && nxt >= 0) pq.push({nxt, v});
}
}
for (auto& e : edges)
ans += min(e[2], used[{e[0], e[1]}] + used[{e[1], e[0]}]);
return ans;
}Explanation
Each original edge [u, v, cnt] is really a chain of cnt tiny nodes between u and v. Rather than build all those nodes, we run Dijkstra on the original nodes tracking how many moves remain when we arrive, and use a max-heap so we always settle the node we can reach with the most moves to spare.
When we settle node u with moves left, we count it (one reachable node). Walking toward neighbor v along an edge of length cnt costs cnt + 1 steps, so we push v with nxt = moves - cnt - 1 if that is still >= 0.
The subdivided nodes on each edge are counted separately. We record used[(u,v)] = min(moves, cnt) — how many of the edge's inner nodes we could walk into from the u side. For each edge the total inner nodes reached is min(cnt, used[(u,v)] + used[(v,u)]), capped so we never double-count the same chain.
The final answer is the original nodes reached plus all those per-edge subdivided contributions.
Example: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6. The 3 original nodes plus 7 + 1 + 2 reachable inner nodes give 13.