Formatted question description: https://leetcode.ca/all/1786.html

1786. Number of Restricted Paths From First to Last Node

Level

Medium

Description

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z_0, z_1, z_2, ..., z_k] such that z_0 = start and z_k = end and there is an edge between z_i and z_(i+1) where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(z_i) > distanceToLastNode(z_(i+1)) where 0 <= i <= k-1.

Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 10^9 + 7.

Example 1:

Image text

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]

Output: 3

Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:

1) 1 –> 2 –> 5

2) 1 –> 2 –> 3 –> 5

3) 1 –> 3 –> 5

Example 2:

Image text

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]

Output: 1

Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 –> 3 –> 7.

Constraints:

  • 1 <= n <= 2 * 10^4
  • n - 1 <= edges.length <= 4 * 10^4
  • edges[i].length == 3
  • 1 <= u_i, v_i <= n
  • u_i != v_i
  • 1 <= weight_i <= 10^5
  • There is at most one edge between any two nodes.
  • There is at least one path between any two nodes.

Solution

Use a hash map to store each node’s adjacent nodes and the corresponding weights. Then use Dijkstra’s algorithm to find the shortest path from node n to each node. Finally, use dynamic programming to find the number of restricted paths that start from node 1 and end at node n.

class Solution {
    static final int MODULO = 1000000007;
    int restrictedPaths = 0;
    int n = 0;
    int[] dp;

    public int countRestrictedPaths(int n, int[][] edges) {
        this.n = n;
        Map<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            List<int[]> list1 = map.getOrDefault(u, new ArrayList<int[]>());
            List<int[]> list2 = map.getOrDefault(v, new ArrayList<int[]>());
            list1.add(new int[]{v, weight});
            list2.add(new int[]{u, weight});
            map.put(u, list1);
            map.put(v, list2);
        }
        int[] distances = getShortestDistances(n, map);
        dp = new int[n + 1];
        dp[n] = 1;
        return backtrack(distances, map, 1);
    }

    public int[] getShortestDistances(int n, Map<Integer, List<int[]>> map) {
        int[] distances = new int[n + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[n] = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer node1, Integer node2) {
                return distances[node1] - distances[node2];
            }
        });
        priorityQueue.offer(n);
        while (!priorityQueue.isEmpty()) {
            int node = priorityQueue.poll();
            int distance = distances[node];
            List<int[]> list = map.getOrDefault(node, new ArrayList<int[]>());
            for (int[] next : list) {
                int nextNode = next[0], weight = next[1];
                if (distance + weight < distances[nextNode]) {
                    distances[nextNode] = distance + weight;
                    priorityQueue.offer(nextNode);
                }
            }
        }
        return distances;
    }

    public int backtrack(int[] distances, Map<Integer, List<int[]>> map, int node) {
        if (dp[node] == 0) {
            int curDistance = distances[node];
            List<int[]> list = map.getOrDefault(node, new ArrayList<int[]>());
            for (int[] next : list) {
                int nextNode = next[0];
                if (distances[nextNode] < curDistance) {
                    int nextCount = backtrack(distances, map, nextNode);
                    dp[node] = (dp[node] + nextCount) % MODULO;
                }
            }
        }
        return dp[node];
    }
}

All Problems

All Solutions