Dijkstra and memo, java solution, beats 99%
\nclass Solution {\n    Integer[]memo;\n    static final int INF = Integer.MAX_VALUE;\n    static final int MOD = (int)(1E9) + 7;\n    public int countRestricte
```\nclass Solution {\n    Integer[]memo;\n    static final int INF = Integer.MAX_VALUE;\n    static final int MOD = (int)(1E9) + 7;\n    public int countRestrictedPaths(int n, int[][] edges) {\n        List<int[]>[]graph = new ArrayList[n];\n        memo = new Integer[n];\n        int[]dis = new int[n];\n        for(int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n        for(int[]e : edges){\n            graph[e[0]-1].add(new int[]{e[1]-1,e[2]});\n            graph[e[1]-1].add(new int[]{e[0]-1,e[2]});\n        }\n        Arrays.fill(dis, INF);\n        dis[n - 1] = 0;\n        Queue<int[]> q = new PriorityQueue<int[]>((a,b)->(a[1] - b[1]));\n        q.add(new int[]{n - 1, 0});\n        while(!q.isEmpty()){\n            int[]node = q.poll();\n            int pos = node[0];\n            int d = node[1];\n            for(int[] u : graph[pos]){\n                int next = u[0];\n                int medium = u[1];\n                if(medium + d < dis[next]){\n                    dis[next] = d + medium;\n                    q.add(new int[]{next, medium + d});\n                }\n            }   \n        }\n        \n        memo[n-1] = 1;\n        \n        return dfs(0, graph, dis);\n    }\n    private int dfs(int node,List<int[]>[]graph, int[]dis){\n        if(memo[node] != null) {\n            return memo[node];\n        }\n        long ans = 0;\n        for(int[]k : graph[node]){\n            if(dis[k[0]] < dis[node]){\n                ans += dfs(k[0], graph, dis);\n            }\n        }\n        memo[node] = (int)(ans % MOD);\n        return memo[node];\n    }\n}\n```
['Memoization']