Dijkstra + DFS approach | Java solution | Clean Code
Complexity\nLet v = number of nodes\ne = number of adges\n- Time complexity: $O((v + e)\log v)$\n Add your time complexity here, e.g. O(n) \n\n- Space complexit
# Complexity\nLet `v = number of nodes`\n`e = number of adges`\n- Time complexity: $O((v + e)\\log v)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(v)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java\nclass Solution {\n    List<List<int[]>> adj;\n    int vals[];\n    int MOD = (int)1e9 + 7;\n    int cnts[];\n    int v;\n    int[] dijkstra(int n,int s){\n        int dist[] = new int[n];\n        Arrays.fill(dist,Integer.MAX_VALUE);\n        dist[s] = 0;\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);\n        pq.add(new int[]{s,0});\n        for(;!pq.isEmpty();){\n            var a = pq.poll();\n            for(var c:adj.get(a[0])){\n                if(dist[c[0]] > a[1] + c[1]){\n                    dist[c[0]] = a[1] + c[1];\n                    pq.add(new int[]{c[0],dist[c[0]]});\n                }\n            }\n        }\n        return dist;\n    } \n    int dfs(int n,int prev){\n        if(vals[n] >= prev) return 0;\n        if(cnts[n] != -1) return cnts[n];\n        if(n == v - 1) return 1;\n        int ans = 0;\n        for(var c:adj.get(n)){\n            ans = (ans + dfs(c[0],vals[n])) % MOD;\n        }\n        return cnts[n] = ans % MOD;\n    }\n    public int countRestrictedPaths(int n, int[][] edges) {\n        adj = new ArrayList<>();\n        cnts = new int[n];\n        Arrays.fill(cnts,-1);\n        v = n;\n        for(int i = 0;i < n;i++){\n            adj.add(new ArrayList<>());\n        }\n        for(var e:edges){\n            adj.get(e[0] - 1).add(new int[]{e[1] - 1,e[2]});\n            adj.get(e[1] - 1).add(new int[]{e[0] - 1,e[2]});\n        }\n        vals = dijkstra(n,n - 1);\n        return dfs(0,Integer.MAX_VALUE) % MOD;\n    }\n}\n```
['Dynamic Programming', 'Depth-First Search', 'Java']