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:**

**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 * 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];
}
}
```