# 882. Reachable Nodes In Subdivided Graph

• Time: $O((|V| + |E|)\log |V|)$
• Space: $O(|E| + |V|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public: int reachableNodes(vector>& edges, int maxMoves, int n) { vector>> graph(n); vector dist(graph.size(), maxMoves + 1); for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; const int cnt = edge[2]; graph[u].emplace_back(v, cnt); graph[v].emplace_back(u, cnt); } const int reachableNodes = dijkstra(graph, 0, maxMoves, dist); int reachableSubnodes = 0; for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; const int cnt = edge[2]; // the number of reachable nodes of edge from u const int a = dist[u] > maxMoves ? 0 : min(maxMoves - dist[u], cnt); // the number of reachable nodes of edge from v const int b = dist[v] > maxMoves ? 0 : min(maxMoves - dist[v], cnt); reachableSubnodes += min(a + b, cnt); } return reachableNodes + reachableSubnodes; } private: int dijkstra(const vector>>& graph, int src, int maxMoves, vector& dist) { using P = pair; // (d, u) priority_queue, greater<>> minHeap; dist[src] = 0; minHeap.emplace(dist[src], src); while (!minHeap.empty()) { const auto [d, u] = minHeap.top(); minHeap.pop(); // Already took maxMoves to reach u, so can't explore anymore. if (d >= maxMoves) break; for (const auto& [v, w] : graph[u]) if (d + w + 1 < dist[v]) { dist[v] = d + w + 1; minHeap.emplace(dist[v], v); } } return ranges::count_if(dist, [&](int d) { return d <= maxMoves; }); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public int reachableNodes(int[][] edges, int maxMoves, int n) { List>[] graph = new List[n]; Queue minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // (d, u) int[] dist = new int[n]; Arrays.fill(dist, maxMoves + 1); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; final int cnt = edge[2]; graph[u].add(new Pair<>(v, cnt)); graph[v].add(new Pair<>(u, cnt)); } final int reachableNodes = dijkstra(graph, 0, maxMoves, dist); int reachableSubnodes = 0; for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; final int cnt = edge[2]; // the number of reachable nodes of edge from u final int a = dist[u] > maxMoves ? 0 : Math.min(maxMoves - dist[u], cnt); // the number of reachable nodes of edge from v final int b = dist[v] > maxMoves ? 0 : Math.min(maxMoves - dist[v], cnt); reachableSubnodes += Math.min(a + b, cnt); } return reachableNodes + reachableSubnodes; } private int dijkstra(List>[] graph, int src, int maxMoves, int[] dist) { // (d, u) Queue> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey)); dist[src] = 0; minHeap.offer(new Pair<>(dist[src], src)); while (!minHeap.isEmpty()) { final int d = minHeap.peek().getKey(); final int u = minHeap.poll().getValue(); // Already took maxMoves to reach u, so can't explore anymore. if (d >= maxMoves) break; for (Pair pair : graph[u]) { final int v = pair.getKey(); final int w = pair.getValue(); if (d + w + 1 < dist[v]) { dist[v] = d + w + 1; minHeap.offer(new Pair<>(dist[v], v)); } } } return (int) Arrays.stream(dist).filter(d -> d <= maxMoves).count(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution: def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int: graph = [[] for _ in range(n)] dist = [maxMoves + 1] * n for u, v, cnt in edges: graph[u].append((v, cnt)) graph[v].append((u, cnt)) reachableNodes = self._dijkstra(graph, 0, maxMoves, dist) reachableSubnodes = 0 for u, v, cnt in edges: # the number of reachable nodes of (u, v) from u a = 0 if dist[u] > maxMoves else min(maxMoves - dist[u], cnt) # the number of reachable nodes of (u, v) from v b = 0 if dist[v] > maxMoves else min(maxMoves - dist[v], cnt) reachableSubnodes += min(a + b, cnt) return reachableNodes + reachableSubnodes def _dijkstra(self, graph: List[List[Tuple[int, int]]], src: int, maxMoves: int, dist: List[int]) -> int: dist[src] = 0 minHeap = [(dist[src], src)] # (d, u) while minHeap: d, u = heapq.heappop(minHeap) # Already took maxMoves to reach u, so can't explore anymore. if dist[u] >= maxMoves: break for v, w in graph[u]: newDist = d + w + 1 if newDist < dist[v]: dist[v] = newDist heapq.heappush(minHeap, (newDist, v)) return sum(d <= maxMoves for d in dist)