✅Dijkstra's Algorithm + Linear DP
IntuitionThe problem ask's to find all restricted paths such that every node in the path follows condition i.e distanceToLastNode(currNode) > distanceToLastNode
# Intuition
The problem ask's to find all restricted paths such that every node in the path follows condition i.e `distanceToLastNode(currNode) > distanceToLastNode(nextNode)`

The very frist thing we need is the min dist from every node to n. If we apply Dijkstra's Algorithm for shorest path  from every node to n, it will be not feasible, since Dijkstra's Algorithm takes `O((V+E)logV) `to find the min dist,, so for all nodes it will be `O(V(V+E)logV) `.
To make it efficient, we will find shorest path from n to any node let's say 1. In the process of finding shorest path from `n to 1`, the algorithm also finds shorest path from n to every other node.
NOW WE HAVE THE DISTANCE ARRAY WITH US.

The next thing we wanna do is to find all the restricted path from 1 to n. The brute force way would be to, first find all the paths from 1 to n and then for every path check the condition if it holds true.
It will obviously result in TLE, we wanna do better than this.

We realize that there are many subproblem in finding paths from 1 to n 
i.e `1->3->4->6->10`  , `1->8->2->4->6->10`,  `1->3->7->9->4->6->10` ....
This give us hint (and even the constrain's) that some dp can be applied.

Let's define dp, `dp[i] = no. of paths from i to 1`, satisfying the condition i.e `distanceToLastNode(currNode) < distanceToLastNode(prevNode)`
**NOTE : we have used reverse condition, since we will be going in backward direction in the path and check if it reachs to 1, if yes return 1 (indicating path is found) else 0 (No path found, which reaches to 1).**


# Approach
1. Find shortest path from n to every other nodes using Dijkstra's Algorithm.
2. Starting from n traverse backward and check how many paths reaches to 1.
3. Use dp to avoid unneccessary computation, if curr node is already visited.

# Complexity
- Time complexity:
O((V+E)logV) + O(V)

- Space complexity:
O(V)

# Code
```java []
class Solution {
    private final int MOD = 1_000_000_007;
    private int dp[];
    public int countRestrictedPaths(int n, int[][] edges) {
        List<int[]> g[] = new ArrayList[n];
        for(int i=0; i<n; i++) g[i] = new ArrayList<>();
        for(int e[] : edges){
            g[e[0]-1].add(new int[]{e[1]-1, e[2]});
            g[e[1]-1].add(new int[]{e[0]-1, e[2]});
        }
        int dist[] = dijkstrasAlgo(g); // Now i have min dist from every node to n.
        // Now for every path from from 1 -> n check if it is a restricted path.

        /* dp[i] = no. of paths from i to 1, which satisfies the condition
         i.e distanceToLastNode[z] < distanceToLastNode[prevZ] */ 

        // so i must reach to 1 from n, reverse order
        this.dp = new int[n];
        Arrays.fill(dp, -1);
        return findPaths(n-1, g, dist);
    }

    private int findPaths(int curr, List<int[]> g[], int dist[]){
        if(curr == 0){
            return 1;
        }
        if(dp[curr] != -1) return dp[curr];
        int res = 0;
        for(int nbr[] : g[curr]){
            if(dist[curr] < dist[nbr[0]]){
                res = (res + findPaths(nbr[0], g, dist) % MOD) % MOD;
            }
        }
        return dp[curr] = res;
    }
    private int[] dijkstrasAlgo(List<int[]> g[]){
        int m = g.length;
        int dist[] = new int[m];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[m-1] = 0;
        boolean vis[] = new boolean[m];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[]{m-1, 0});
        while(!pq.isEmpty()){
            int curr[] = pq.poll();
            if(!vis[curr[0]]){
                vis[curr[0]] = true;
                for(int nbr[] : g[curr[0]]){
                    int nbrCost = nbr[1] + curr[1];
                    if(nbrCost < dist[nbr[0]]){
                        dist[nbr[0]] = nbrCost;
                        pq.offer(new int[]{nbr[0], nbrCost});
                    }
                }
            }
        }
        return dist;
    }
}   
```
['Dynamic Programming', 'Shortest Path', 'Java']