# LeetCode 1786. Number of Restricted Paths From First to Last Node



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:**![](https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex1.png)

```
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:**![](https://assets.leetcode.com/uploads/2021/02/17/restricted_paths_ex22.png)

```
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 <= ui, vi <= n`
* `ui != vi`
* `1 <= weighti <= 10^5`
* There is at most one edge between any two nodes.
* There is at least one path between any two nodes.

## Solution:

[English Version in Youtube](https://youtu.be/b0YQ-IQbX1k)

[中文版解答Youtube Link](https://youtu.be/_NW5IRZtdOY)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1Xv411h74T/)

```
class Solution {
public:
    
    void bfs(int n, const vector<vector<pair<int, int>>>& graph, vector<int>& distances, vector<int>& closest_nodes) {
        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) {
            return a.second > b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        vector<bool> visited(n+1, false);
        pq.push({n, 0});
        
        while (!pq.empty()) {
            pair<int, int> current = pq.top();
            pq.pop();
            int node = current.first;
            int dis = current.second;
            if (visited[node] == true) {
                continue;
            }
            distances[node] = dis;
            visited[node] = true;
            closest_nodes.push_back(node);
            
            for (pair<int, int> neighbor : graph[node]) {
                int neighbor_node = neighbor.first;
                if (visited[neighbor_node] == false) {
                    pq.push({neighbor_node, dis + neighbor.second});
                }
            }
        }
    }
    
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> graph(n+1);
        for (const vector<int>& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            graph[edge[1]].push_back({edge[0], edge[2]});
        }
        
        vector<int> distances(n + 1, 0);
        vector<int> closest_nodes;
        bfs(n, graph, distances, closest_nodes);
        
        vector<long> dp(n+1, 0);
        dp[1] = 1;
        int mod = 1e9+7;
        for (int i = closest_nodes.size() - 1; i >= 0; i--) {
            int node = closest_nodes[i];
            for (pair<int, int> neighbor : graph[node]) {
                int neighbor_node = neighbor.first;
                if (distances[neighbor_node] < distances[node]) {
                    dp[neighbor_node] += dp[node];
                    dp[neighbor_node] %= mod;
                }
            }
        }
        
        return dp[n];
    }
};
```
