1786. Number of Restricted Paths From First to Last Node

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] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti.

A path from node start to node end is a sequence of nodes [z0, z1,z2, ..., zk] such that z0 = start and zk = end and there is an edge between zi and zi+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(zi) > distanceToLastNode(zi+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 109 + 7.

 

Example 1:

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:

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 * 104
• n - 1 <= edges.length <= 4 * 104
• edges[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 1 <= weighti <= 105
• There is at most one edge between any two nodes.
• There is at least one path between any two nodes.

 

Solutions

Solution: Depth-First Search

• Time complexity: O(mlogn)
• Space complexity: O(m+n)

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
const countRestrictedPaths = function (n, edges) {
  const MODULO = 10 ** 9 + 7;
  const graph = edges.reduce((map, [u, v, weight]) => {
    (map[u] = map[u] ?? []).push({ edge: v, weight });
    (map[v] = map[v] ?? []).push({ edge: u, weight });
    return map;
  }, {});
  const queue = [n];
  const distances = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
  const status = new Array(n + 1).fill('not visited');
  const countMap = new Map([[n, 1]]);
  const restrictedPaths = node => {
    if (countMap.has(node)) return countMap.get(node);
    const count = graph[node].reduce((result, { edge }) => {
      const num = distances[edge] < distances[node] ? restrictedPaths(edge) : 0;

      return (result + num) % MODULO;
    }, 0);

    countMap.set(node, count);
    return count;
  };

  distances[n] = 0;
  while (queue.length) {
    const node = queue.shift();

    status[node] = 'start';
    for (const { edge, weight } of graph[node]) {
      if (distances[node] + weight >= distances[edge]) continue;
      distances[edge] = distances[node] + weight;
      status[edge] === 'not visited' && queue.push(edge);
      status[edge] === 'start' && queue.unshift(edge);
      status[edge] = 'visited';
    }
  }
  return restrictedPaths(1);
};