# 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 * 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.

有权无向图包含标记为\[1, n]的n个节点， distanceToLastNode(x)表示从x点到n点最短距离，一条restricted path表示其中每个节点都满足distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1的路径，问图中一共有多少条restricted path。先求出每个节点的distanceToLastNode作为节点值，用Dijkstra。此时问题转化为找所有满足路径上节点值单调减的路径：找所有=>DFS。并且从任意一点开始的路径数一旦确定，它的值就可以cached以复用=>cached DFS。

```python
from heapq import heappush, heappop

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        d, g = [float('inf')] * (n + 1), collections.defaultdict(list)
        for i, (a, b, w) in enumerate(edges):
            g[a].append((b, w))
            g[b].append((a, w))
        d[n] = 0
        heap = [(d[n], n)]
        while heap:
            dis, cur = heappop(heap)
            for nei, w in g[cur]:
                cand = dis + w
                if cand < d[nei]:
                    d[nei] = cand
                    heappush(heap, (d[nei], nei))
        res, M, visited = [0], 10 ** 9 + 7, [-1] * (n + 1)
        def dfs(cur, g, e, res):
            if visited[cur] != -1:
                return visited[cur]
            visited[cur] = 0
            if cur == e:
                visited[cur] = 1
                return visited[cur]
            for nei, _ in g[cur]:
                if d[nei] <= d[cur]:
                    continue
                visited[cur] = (visited[cur] % M + dfs(nei, g, e, res) % M) % M
            return visited[cur]
        return dfs(n, g, 1, res)
                
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/graph/1786.-number-of-restricted-paths-from-first-to-last-node.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.