#1786

Number of Restricted Paths From First to Last Node

expert · 1015 · lc medium +32 · verified · 41% accepted · 1,194 likes · top 21%

Description

In an undirected weighted connected graph with n nodes, let distanceToLastNode(x) be the shortest-path distance from x to node n. A restricted path from 1 to n has distanceToLastNode(zi) > distanceToLastNode(zi+1) for each step. Return the count modulo 10⁹ + 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.

Code

1

2

3

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int: