# 1786. Number of Restricted Paths From First to Last Node
###### tags: `Leetcode` `Medium` `BFS` `Dynamic Programming` `Dijkstra`
Link: https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/
## 思路
先用dijkstra找到每个从node n到其他node的最短距离
然后用dp找到最短路径的个数
## Code

class Solution {
    public int countRestrictedPaths(int n, int[][] edges) {
        //dijkstra
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int[] edge:edges){
            int s = edge[0], t = edge[1], w = edge[2];
            graph.get(s).add(new int[]{t,w});
            graph.get(t).add(new int[]{s,w});
        }
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        pq.add(new int[]{n,0});
        int[] shortestDist = new int[n+1];
        Arrays.fill(shortestDist, Integer.MAX_VALUE);
        shortestDist[n]=0;
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            for(int[] neighbor:graph.get(curr[0])){
                if(curr[1]+neighbor[1]<shortestDist[neighbor[0]]){
                    shortestDist[neighbor[0]] = curr[1]+neighbor[1];
                    pq.add(new int[]{neighbor[0],shortestDist[neighbor[0]]});
                }
            }
        }
        
        //dfs dp
        Integer[] dp = new Integer[n];
        return dfs(1, n, shortestDist, graph, dp);
    }
    private int dfs(int start, int end, int[] shortestDist, List<List<int[]>> graph, Integer[] dp){
        int mod = 1000000007;
        long res = 0;
        if(start==end) return 1;
        if(dp[start]!=null) return dp[start];
        for(int[] next:graph.get(start)){
            if(shortestDist[start]>shortestDist[next[0]])
                res += dfs(next[0], end, shortestDist, graph, dp);
                res = res%mod;
        } 
        dp[start] = (int)res;
        return (int)(dp[start]%mod);
    }
}