Share My Java Dijkstra + DFS (w/ cache) Solution
It took me a long time to understand the question...\n\n\n// Dijkstra + DFS with cache\npublic int countRestrictedPaths(int n, int[][] edges) {\n\tif (n <= 0 ||
It took me a long time to understand the question...\n\n```\n// Dijkstra + DFS with cache\npublic int countRestrictedPaths(int n, int[][] edges) {\n\tif (n <= 0 || edges == null || edges.length == 0) return 0;\n\n\t// step 1. build graph\n\tMap<Integer, Map<Integer, Integer>> map = new HashMap<>();  // from -> {to -> weight}\n\tfor (int[] edge : edges) {\n\t\tmap.putIfAbsent(edge[0], new HashMap<>());\n\t\tmap.putIfAbsent(edge[1], new HashMap<>());\n\n\t\tmap.get(edge[0]).put(edge[1], edge[2]);\n\t\tmap.get(edge[1]).put(edge[0], edge[2]);\n\t} \n\n\t// step 2. Dijkstra \n\t// start from node n, to caluclate min distance from x to n\n\tint[] dist = new int[n+1];  // node 1 ~ n\n\tdist[n] = 0;\n\tPriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);    // pq of {x, dist}\n\tpq.offer(new int[]{n, 0});  // start from n, weight is 0.\n\twhile (!pq.isEmpty()) {\n\t\tint[] cur = pq.poll();\n\t\tint node = cur[0];\n\t\tint weight = cur[1];\n\n\t\tMap<Integer, Integer> nexts = map.get(node);\n\t\tfor (int next : nexts.keySet()) {\n\t\t\tif (next == n) continue;    // skip the final node\n\n\t\t\tint nextWeight = weight + nexts.get(next);\n\t\t\tif (dist[next] == 0 || nextWeight < dist[next]) {\n\t\t\t\tpq.offer(new int[]{next, nextWeight});\n\t\t\t\tdist[next] = nextWeight;\n\t\t\t}\n\t\t}\n\t}\n\n\t// step 3. DFS + cache to count restricted path\n\tint[] dp = new int[n+1];\n\tArrays.fill(dp, -1);\n\treturn dfs(1, n, map, dist, dp);\n}\n\nprivate int dfs(int node, int n, Map<Integer, Map<Integer, Integer>> map, int[] dist, int[] dp) {\n\tif (node == n) return 1;    // reach n, means this is 1 restricted path\n\n\tif (dp[node] != -1) return dp[node];\n\n\tint count = 0;\n\tint weight = dist[node];\n\tMap<Integer, Integer> nexts = map.get(node);\n\tfor (int next : nexts.keySet()) {\n\t\tint nextWeight = dist[next];\n\t\tif (nextWeight < weight) {\n\t\t\tcount = (count + dfs(next, n, map, dist, dp)) % 1000000007;\n\t\t}\n\t}\n\n\tdp[node] = count;\n\treturn count;\n}\n```
[]