[Python/Java] Dijkstra & Cached DFS - Clean & Concise
Idea\n- We use Dijkstra to calculate shortest distance paths from last node n to any other nodes x, the result is distanceToLastNode(x), where x in 1..n. Comple
**Idea**\n- We use Dijkstra to calculate shortest distance paths from last node `n` to any other nodes `x`, the result is `distanceToLastNode(x)`, where `x in 1..n`. Complexity: `O(E * logV) = O(M logN)`, where `M` is number of edges, `N` is number of nodes.\n- In the restricted path, `[z0, z1, z2, ..., zk]`,  node `zi` always stand before node `z(i+1)` because `distanceToLastNode(zi) > distanceToLastNode(zi+1)`, mean while `dfs` do calculate number of paths, a `current node` never comeback to `visited nodes`, so we don\'t need to use `visited` array to check visited nodes. Then our `dfs(src)` function only depends on one param `src`, we can use memory cache to cache precomputed results of `dfs` function, so the time complexity can be deduced to be `O(E)`.\n\n**Complexity:**\n- Time: `O(M * logN)`, where `M` is number of edges, `N` is number of nodes.\n- Space: `O(M + N)`\n\n**Python 3**\n```python\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        if n == 1: return 0\n        graph = defaultdict(list)\n        for u, v, w in edges:\n            graph[u].append((w, v))\n            graph[v].append((w, u))\n\n        def dijkstra():  # Dijkstra to find shortest distance of paths from node `n` to any other nodes\n            minHeap = [(0, n)]  # dist, node\n            dist = [float(\'inf\')] * (n + 1)\n            dist[n] = 0\n            while minHeap:\n                d, u = heappop(minHeap)\n                if d != dist[u]: continue\n                for w, v in graph[u]:\n                    if dist[v] > dist[u] + w:\n                        dist[v] = dist[u] + w\n                        heappush(minHeap, (dist[v], v))\n            return dist\n\n        @lru_cache(None)\n        def dfs(src):\n            if src == n: return 1  # Found a path to reach to destination\n            ans = 0\n            for _, nei in graph[src]:\n                if dist[src] > dist[nei]:\n                    ans = (ans + dfs(nei)) % 1000000007\n            return ans\n        \n        dist = dijkstra()\n        return dfs(1)\n```\n\n**Java**\n```java\nclass Solution {\n    public int countRestrictedPaths(int n, int[][] edges) {\n        if (n == 1) return 0;\n        List<int[]>[] graph = new List[n+1];\n        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();\n        for (int[] e : edges) {\n            graph[e[0]].add(new int[]{e[2], e[1]});\n            graph[e[1]].add(new int[]{e[2], e[0]});\n        }\n        int[] dist = dijkstra(n, graph);\n        return dfs(1, n, graph, dist, new Integer[n+1]);\n    }\n    // Dijkstra to find shortest distance of paths from node `n` to any other nodes\n    int[] dijkstra(int n, List<int[]>[] graph) {\n        int[] dist = new int[n+1];\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        dist[n] = 0;\n        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // dist, node\n        minHeap.offer(new int[]{0, n});\n        while (!minHeap.isEmpty()) {\n            int[] top = minHeap.poll();\n            int d = top[0], u = top[1];\n            if (d != dist[u]) continue;\n            for (int[] nei : graph[u]) {\n                int w = nei[0], v = nei[1];\n                if (dist[v] > dist[u] + w) {\n                    dist[v] = dist[u] + w;\n                    minHeap.offer(new int[]{dist[v], v});\n                }\n            }\n        }\n        return dist;\n    }\n    int dfs(int src, int n, List<int[]>[] graph, int[] dist, Integer[] memo) {\n        if (memo[src] != null) return memo[src];\n        if (src == n) return 1; // Found a path to reach to destination\n        int ans = 0;\n        for (int[] nei : graph[src]) {\n            int w = nei[0], v = nei[1];\n            if (dist[src] > dist[v])\n                ans = (ans + dfs(v, n, graph, dist, memo)) % 1000000007;\n        }\n        return memo[src] = ans;\n    }\n}\n```\n
[]