1786. Number of Restricted Paths From First to Last Node
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
import heapq
from collections import defaultdict

MOD = 10**9 + 7

class Solution:
    def countRestrictedPaths(self, n, edges):
        if n == 1:
            return 0
        
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((w, v))
            graph[v].append((w, u))

        dist = [float('inf')] * (n + 1)
        dist[n] = 0
        pq = [(0, n)]

        while pq:
            d, node = heapq.heappop(pq)
            if dist[node] < d:
                continue
            for weight, neighbor in graph[node]:
                if dist[neighbor] > dist[node] + weight:
                    dist[neighbor] = dist[node] + weight
                    heapq.heappush(pq, (dist[neighbor], neighbor))

        dp = [-1] * (n + 1)

        def find_paths(node):
            if node == n:
                return 1
            if dp[node] != -1:
                return dp[node]
            path_count = 0
            for _, neighbor in graph[node]:
                if dist[node] > dist[neighbor]:
                    path_count = (path_count + find_paths(neighbor)) % MOD
            dp[node] = path_count
            return path_count

        return find_paths(1)

```
['Python3']