Practice/Google/Leetcode 1786. Number of Restricted Paths From First to Last Node

Leetcode 1786. Number of Restricted Paths From First to Last Node

CodingMust

Problem

You are given an undirected weighted graph with n nodes labeled from 1 to n, and a list of edges where each edge is represented as [u, v, weight], indicating a bidirectional edge between nodes u and v with the given weight.

A restricted path is a path from node 1 to node n such that:

• The path starts at node 1 and ends at node n
• For every consecutive pair of nodes in the path, the shortest distance from the current node to node n is strictly greater than the shortest distance from the next node to node n

In other words, as you traverse the path, you must always move to a node that is strictly closer to the destination (node n) in terms of shortest path distance.

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

Requirements

1. Build an adjacency list representation of the graph
2. Calculate the shortest distance from every node to node n using an appropriate shortest path algorithm
3. Count all valid paths from node 1 to node n where the distance-to-destination strictly decreases at each step
4. Return the count modulo 10^9 + 7
5. Handle graphs where no valid path exists (return 0)

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 from node 1 to node n

Examples

Example 1:

` Input: n = 3, edges = [[1,2,3],[2,3,1],[1,3,4]] Output: 3 Explanation:

• Shortest distances to node 3: dist[1]=4, dist[2]=1, dist[3]=0
• Valid paths where distance strictly decreases:
  1. 1 -> 3 (distance goes from 4 to 0)
  2. 1 -> 2 -> 3 (distance goes from 4 to 1 to 0) Total: 2 paths (note: actual calculation may vary based on graph structure) `

Example 2:

` Input: n = 4, edges = [[1,2,1],[2,3,1],[3,4,1]] Output: 1 Explanation:

• Shortest distances: dist[1]=3, dist[2]=2, dist[3]=1, dist[4]=0
• Only valid path: 1 -> 2 -> 3 -> 4 (distances: 3 -> 2 -> 1 -> 0) `

Example 3:

Input: n = 2, edges = [[1,2,100]] Output: 1 Explanation: Only one path exists: 1 -> 2