882. Reachable Nodes In Subdivided Graph

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the shortest distances from node 0 to all other nodes in the graph. Then, we can iterate through each edge and calculate how many nodes are reachable based on the number of subdivisions and the distances between nodes.

Initialize a distance array to store the shortest distance from node 0 to all other nodes. Initialize it with a maximum value except for node 0 where distance is 0.
Implement Dijkstra's algorithm to find the shortest distances from node 0 to all other nodes.
Iterate through each edge in the original graph and calculate the number of reachable nodes based on the subdivisions and distances.
Keep track of the total reachable nodes and return the count.

Time Complexity: O(n^2 log n) where n is the number of nodes
Space Complexity: O(n^2)

View Leetcode Problem

class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, cnt);
            graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, cnt);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0}); // distance, node
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], node = curr[1];
            if (d > dist[node]) continue;
            
            for (int neighbor : graph.getOrDefault(node, new HashMap<>()).keySet()) {
                int cnt = graph.get(node).get(neighbor);
                int newDist = d + cnt + 1;
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{newDist, neighbor});
                }
            }
        }
        
        int ans = 0;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            int reachable = Math.min(cnt, Math.max(0, maxMoves - dist[u])) + Math.min(cnt, Math.max(0, maxMoves - dist[v]));
            ans += Math.min(reachable, cnt);
        }
        
        for (int d : dist) {
            if (d <= maxMoves) ans++;
        }
        
        return ans;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution