Problem Description

Given an undirected graph described by edges, where each edge [u, v, cnt] means there is an edge between nodes u and v that is subdivided into cnt new nodes (i.e., the edge becomes a path of cnt + 1 edges and cnt new nodes in between), and an integer maxMoves, your task is to determine how many nodes (including both original and subdivided nodes) are reachable from node 0 using at most maxMoves moves.

Constraints:

• Each move traverses from one node to an adjacent node (either original or subdivided).
• You may revisit nodes and edges, but each subdivided node is unique to its edge and position.
• You cannot exceed maxMoves in total moves from node 0.
• Return the total number of distinct nodes (original and subdivided) reachable from node 0.

Thought Process

At first glance, the problem seems to require expanding the entire graph to include all subdivided nodes, then performing a breadth-first or depth-first search to count the number of reachable nodes from node 0 within maxMoves steps. However, explicitly building the subdivided graph is inefficient, especially if edge subdivision counts are large.

Instead, we need an approach that efficiently simulates traversals over subdivided edges without actually creating all the intermediate nodes. We realize that each edge can be traversed partially (i.e., we may only reach some subdivided nodes along an edge, depending on our remaining moves), and we need to account for all such reachable nodes.

The problem reduces to a shortest-path computation (like Dijkstra's algorithm) on the original graph, treating the edge weights as the number of subdivided nodes plus one (the length of the subdivided edge). Then, for each edge, we can compute how many subdivided nodes are reached from each side, and sum up all reachable nodes.

Solution Approach

We use a modified Dijkstra's algorithm to track the maximum number of moves remaining when reaching each node, and efficiently count reachable subdivided nodes on each edge.

1. Graph Representation:
   • Build an adjacency list for the original graph, where each edge stores the number of subdivided nodes (cnt).
2. Dijkstra's Algorithm:
   • Use a max-heap (priority queue) to always expand the node with the most moves left.
   • For each node, track the maximum moves left when reaching it. Skip if we've already reached it with more moves before.
3. Counting Reachable Nodes:
   • Every time we pop a node from the heap, we know it's reachable, so count it.
   • For each edge [u, v, cnt], track how many subdivided nodes are reached from u and from v (based on remaining moves after reaching those nodes).
   • The total reachable subdivided nodes on edge [u, v] is min(cnt, used_from_u + used_from_v), where used_from_u and used_from_v are the moves spent into the edge from each side.
4. Final Count:
   • Sum all original nodes reached, plus all reachable subdivided nodes across all edges.

This method avoids explicit graph expansion and efficiently traverses only what is necessary.

Example Walkthrough

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

1. Build the adjacency list:
   • 0: [(1,4), (2,8)]
   • 1: [(0,4), (2,6)]
   • 2: [(1,6), (0,8)]
2. Start Dijkstra's from node 0 with 10 moves left.
3. From 0, can reach:
   • 1: needs 5 moves (4 subdivided nodes + 1 = 5), so moves left at 1 = 10 - 5 = 5
   • 2: needs 9 moves (8 subdivided nodes + 1 = 9), so moves left at 2 = 10 - 9 = 1
4. Visit 1 (with 5 moves left): can reach 2 via edge (1,2,6), which requires 7 moves (6+1), but only have 5, so can't reach 2 from here. However, can use up to 5 moves into the subdivided nodes along (1,2).
5. Visit 2 (with 1 move left): can use up to 1 move into the subdivided nodes along (2,1) and (2,0).
6. For each edge, sum up the reachable subdivided nodes from both sides, not exceeding the total subdivided nodes on that edge.
7. Total reachable nodes = original nodes reached (0,1,2) + subdivided nodes reached on each edge.

Time and Space Complexity

Brute-force approach:

• If we explicitly expand each subdivided edge, the number of nodes can be huge (sum of all cnt), making BFS/DFS O(L), where L is the total number of nodes after subdivision.
• Space complexity is also O(L).

• We process each original node at most once, and each edge at most twice (once from each side), so time complexity is O(E log N), where E is the number of edges and N is the number of original nodes.
• Space complexity is O(N + E), for the graph and bookkeeping structures.

This is much more efficient and scalable for large graphs and high subdivision counts.

Summary

The key insight is to simulate traversals over subdivided edges without explicitly generating the subdivided nodes. By using Dijkstra's algorithm and carefully tracking moves left at each node, we can efficiently count all reachable original and subdivided nodes. This approach avoids the combinatorial explosion of brute-force expansion, resulting in an elegant and efficient solution.

Code Implementation

import heapq
from collections import defaultdict

class Solution:
    def reachableNodes(self, edges, maxMoves, n):
        graph = defaultdict(list)
        for u, v, cnt in edges:
            graph[u].append((v, cnt))
            graph[v].append((u, cnt))
        
        heap = [(-maxMoves, 0)]  # (neg moves left, node)
        seen = dict()
        while heap:
            neg_moves, node = heapq.heappop(heap)
            moves = -neg_moves
            if node in seen and seen[node] >= moves:
                continue
            seen[node] = moves
            for nei, cnt in graph[node]:
                next_moves = moves - cnt - 1
                if next_moves >= 0 and (nei not in seen or seen[nei] < next_moves):
                    heapq.heappush(heap, (-next_moves, nei))
        
        ans = len(seen)  # Original nodes reached
        used = dict()
        for u, v, cnt in edges:
            a = seen.get(u, 0)
            b = seen.get(v, 0)
            ans += min(cnt, a + b)
        return ans
      

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<pair<int,int>>> graph(n);
        for (auto& e : edges) {
            graph[e[0]].push_back({e[1], e[2]});
            graph[e[1]].push_back({e[0], e[2]});
        }
        priority_queue<pair<int,int>> pq;
        unordered_map<int,int> seen;
        pq.push({maxMoves, 0});
        while (!pq.empty()) {
            auto [moves, node] = pq.top(); pq.pop();
            if (seen.count(node) && seen[node] >= moves) continue;
            seen[node] = moves;
            for (auto& [nei, cnt] : graph[node]) {
                int next_moves = moves - cnt - 1;
                if (next_moves >= 0 && (!seen.count(nei) || seen[nei] < next_moves)) {
                    pq.push({next_moves, nei});
                }
            }
        }
        int ans = seen.size();
        for (auto& e : edges) {
            int a = seen.count(e[0]) ? seen[e[0]] : 0;
            int b = seen.count(e[1]) ? seen[e[1]] : 0;
            ans += min(e[2], a + b);
        }
        return ans;
    }
};
      

import java.util.*;

class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] e : edges) {
            graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(new int[]{e[1], e[2]});
            graph.computeIfAbsent(e[1], k -> new ArrayList<>()).add(new int[]{e[0], e[2]});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        Map<Integer, Integer> seen = new HashMap<>();
        pq.offer(new int[]{maxMoves, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int moves = curr[0], node = curr[1];
            if (seen.containsKey(node) && seen.get(node) >= moves) continue;
            seen.put(node, moves);
            if (!graph.containsKey(node)) continue;
            for (int[] nei : graph.get(node)) {
                int next_moves = moves - nei[1] - 1;
                if (next_moves >= 0 && (!seen.containsKey(nei[0]) || seen.get(nei[0]) < next_moves)) {
                    pq.offer(new int[]{next_moves, nei[0]});
                }
            }
        }
        int ans = seen.size();
        for (int[] e : edges) {
            int a = seen.getOrDefault(e[0], 0);
            int b = seen.getOrDefault(e[1], 0);
            ans += Math.min(e[2], a + b);
        }
        return ans;
    }
}
      

/**
 * @param {number[][]} edges
 * @param {number} maxMoves
 * @param {number} n
 * @return {number}
 */
var reachableNodes = function(edges, maxMoves, n) {
    const graph = new Map();
    for (let [u, v, cnt] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        if (!graph.has(v)) graph.set(v, []);
        graph.get(u).push([v, cnt]);
        graph.get(v).push([u, cnt]);
    }
    const maxHeap = [[maxMoves, 0]];
    const seen = new Map();
    while (maxHeap.length) {
        maxHeap.sort((a, b) => b[0] - a[0]);
        let [moves, node] = maxHeap.shift();
        if (seen.has(node) && seen.get(node) >= moves) continue;
        seen.set(node, moves);
        if (!graph.has(node)) continue;
        for (let [nei, cnt] of graph.get(node)) {
            let next_moves = moves - cnt - 1;
            if (next_moves >= 0 && (!seen.has(nei) || seen.get(nei) < next_moves)) {
                maxHeap.push([next_moves, nei]);
            }
        }
    }
    let ans = seen.size;
    for (let [u, v, cnt] of edges) {
        let a = seen.get(u) || 0;
        let b = seen.get(v) || 0;
        ans += Math.min(cnt, a + b);
    }
    return ans;
};