DevExCode

Sign in to devexcode.com with google.com

To continue, google.com will share your name, email address, and profile picture with this site. See this site's privacy policy.

1786. Number of Restricted Paths From First to Last Node

Dynamic ProgrammingGraphTopological SortHeap (Priority Queue)Shortest Path

Explanation:

To solve this problem, we can use Dijkstra's algorithm to find the shortest distance from node n to all other nodes. Then, we can use dynamic programming to count the number of restricted paths from node 1 to node n based on the shortest distances computed.

  1. Compute the shortest distances from node n to all other nodes using Dijkstra's algorithm.
  2. Initialize an array dp to store the number of restricted paths from node 1 to each node.
  3. Iterate over the nodes in decreasing order of shortest distance from node n.
  4. For each node u in the iteration, loop through its neighbors v and update dp[u] based on the sum of dp[v] if the distance to v is greater than the distance to u.
  5. Return dp[1] as the number of restricted paths from node 1 to node n.

Time complexity: O(ElogN) where E is the number of edges and N is the number of nodes. Space complexity: O(N)

View Leetcode Problem
class Solution {
    public int countRestrictedPaths(int n, int[][] edges) {
        int mod = 1000000007;
        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[] {edge[1], edge[2]});
            graph[edge[1]].add(new int[] {edge[0], edge[2]});
        }
        
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[] {n, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0];
            for (int[] neighbor : graph[u]) {
                int v = neighbor[0];
                int weight = neighbor[1];
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[] {v, dist[v]});
                }
            }
        }
        
        int[] dp = new int[n + 1];
        dp[n] = 1;
        
        int[] order = new int[n];
        for (int i = 1; i <= n; i++) {
            order[i - 1] = i;
        }
        Arrays.sort(order, (a, b) -> dist[a] - dist[b]);
        
        for (int u : order) {
            for (int[] neighbor : graph[u]) {
                int v = neighbor[0];
                if (dist[v] > dist[u]) {
                    dp[u] = (dp[u] + dp[v]) % mod;
                }
            }
        }
        
        return dp[1];
    }
}

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.

Previous QuestionNext Question