Python3 - Beats 100%- Dijkstra's algorithm + Dynamic Programming (BFS, heap, memoization)
IntuitionThis problem will require finding the shortest path from the end node to all other nodes. To do this, we will use Dijkstra's algorithm (BFS + Priority
# Intuition
This problem will require finding the shortest path from the end node to all other nodes. To do this, we will use Dijkstra's algorithm (BFS + Priority Queue).

At that point, we can simply use dynamic programming to figure out the number of paths from 1 - n that meet the restricted condition.

To be extremely efficient, we can do this memoization during the BFS traversal.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1. Set `MOD` to $$10^9 + 7$$
2. Build undirected graph using a dictionary containing lists by iterating through edges, appending a tuple of `(weight, destination node)` to the list for key `source node`. Since it is undirected, add an entry to `u` for `v` and `v` for `u`.
3. Initialize distance array of size `n+1` set to positive infinity and set `distance[n]` to `0` (since we are finding distance FROM `n`)
4. Initialize `dp` as an array for memoization/DP to track number of paths from `i` to `n`
5. Initialize priority queue that holds `(current weight, node)`
6. Process priority queue, every iteration:
    - Pop node and current weight with smallest weight (dijkstra's)
    - Skip if current weight is greater than distance noted in `distance[node]`.
    - Process `node`'s neighbors in the graph. 
        - If neighbor's weight + distance recorded for node is less than distance recorded for neighboring node, mark `distance[nnode]` with that weight and push the neighboring node into the min-heap.
        - Else, if current node's path weight is greater than distance recorded for neighbor node, set `dp[node]` equal to `dp[node] + dp[nnode] % MOD`.
    - If you've reached node 1, break the loop
7. Return `dp[1]`, as this will return the number of restricted paths to `n`
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```python3 []
class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        MOD = 10**9 + 7 # Return MOD of answer

        # Build Undirected Graph where graph[node_a] -> (weight, node_b) shows a connection
        graph = {x:[] for x in range(1, n+1)}
        for u, v, weight in edges:
            graph[u].append((weight, v))
            graph[v].append((weight, u))

        # Distance array to track shortest distance from starting node to node at index i
        distance = [inf] * (n+1)
        distance[n] = 0

        # DP array for Memoization of number of paths from 1-n
        dp = [0] * (n+1)
        dp[n] = 1

        # Combine Dijkstra's formula (min heap + BFS) with DP

        pq = [(0, n)]   # Priority Queue (min-heap) for BFS
        # Process pq
        while pq:
            # Get the node with the smallest distance
            weight, node = heappop(pq)
            
            # If the current path is longer than already known path to node, move on
            if weight > distance[node]:
                continue
            
            # Process next node's, updating the distance to next node if smaller than currently known paths.
            # If a shorter path is found, add the next node to min-heap/pq to process further.
            # If current path distance is greater than shortest path to neighbor, update dp table
            for nweight, nnode in graph[node]:
                new_weight = nweight + distance[node]
                if new_weight < distance[nnode]:
                    distance[nnode] = new_weight
                    heappush(pq, (new_weight, nnode))
                elif weight > distance[nnode]:
                    dp[node] = (dp[node] + dp[nnode]) % MOD
        
            if node == 1:
                break
        
        return dp[1]
```
['Dynamic Programming', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'Python3']