Very Easy Check Once
IntuitionThe problem requires counting paths from node1to noden, with the restriction that each step must move to a node with a strictly smaller shortest distan
## **Intuition**
The problem requires counting paths from node **1** to node **n**, with the restriction that each step must move to a node with a strictly smaller shortest distance to node **n**. 

1. First, compute the shortest path from **n** to all other nodes using **Dijkstra’s Algorithm**.
2. Then, use **DFS with memoization** to count the valid paths from **1** to **n**, ensuring that we only move to nodes with a strictly larger shortest path distance.

---

## **Approach**
1. **Graph Representation**  
   - Use an **adjacency list** where `adj[i]` stores `(neighbor, weight)` pairs for each node `i`.

2. **Dijkstra’s Algorithm**  
   - Initialize an array `dist[]` to store the shortest distance from **node n** to all other nodes.
   - Use a **min-heap (priority queue)** to process nodes based on increasing distance.
   - Relax edges to compute shortest paths.

3. **DFS with Memoization**  
   - Define a recursive function `a(adj, dist, dp, node)`, where:
     - `adj` stores the graph.
     - `dist` contains the shortest distances from `n` to all nodes.
     - `dp[i]` memoizes the count of valid paths from `i` to `n`.
   - Start DFS from node **1**.
   - At each node, iterate over its neighbors and move only if `dist[neighbor] > dist[current]`.
   - Return the total number of valid paths modulo **10⁹ + 7**.

---

## **Complexity Analysis**
- **Dijkstra’s Algorithm**:  
  - Uses a **priority queue** (min-heap), leading to **O((E + V) log V)** time complexity.
- **DFS with Memoization**:  
  - Each node is visited once in the worst case, giving **O(V + E)** time complexity.
- **Overall Complexity**:  
  - **O((E + V) log V) + O(V + E) ≈ O((E + V) log V)**.

- **Space Complexity**:  
  - **O(V + E)** for adjacency list.  
  - **O(V)** for `dist[]` and `dp[]`.  
  - **O(V)** recursion depth in the worst case.  
  - **Total: O(V + E)**.

# Code
```java []
class Solution {
    public int countRestrictedPaths(int n, int[][] edges) {
        List<List<int[]>> adj=new ArrayList<>();
        for(int i=0;i<=n;i++)adj.add(new ArrayList<>());
        for(int[]a:edges){
            adj.get(a[0]).add(new int[]{a[1],a[2]});
            adj.get(a[1]).add(new int[]{a[0],a[2]});
        }
        int[]dist=new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[n]=0;
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[1]-b[1]);
        pq.add(new int[]{n,0});
        while(!pq.isEmpty()){
            int[]curr=pq.poll();
            if(curr[1]>dist[curr[0]])continue;
            for(int[]a:adj.get(curr[0])){
                if(curr[1]+a[1]<dist[a[0]]){
                    dist[a[0]]=curr[1]+a[1];
                    pq.add(new int[]{a[0],dist[a[0]]});
                }
            }
        }
        int[]dp=new int[n+1];
        Arrays.fill(dp,-1);
        return a(adj,dist,dp,n);
    }
    public int a(List<List<int[]>> adj,int[]dist,int[]dp,int n){
        if(n==1)return 1;
        if(dp[n]!=-1)return dp[n];
        int c=0;
        for(int[]a:adj.get(n)){
            if(dist[a[0]]>dist[n]){
                c=(c+a(adj,dist,dp,a[0]))%1000000007;
            }
        }
        return dp[n]=c;
    }
}
```
['Dynamic Programming', 'Graph', 'Topological Sort', 'Heap (Priority Queue)', 'Shortest Path', 'Java']