Clean Java
This question is a combination of \n\n1. 787. Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops/\n2. cout of increas
This question is a combination of \n\n1. 787. Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops/\n2. cout of increasing path\n\n\nwe first use dijikstra to calculate the distance to last node value of every node\nthen we do a dfs from 1 to n, use memo to cache.\n\n```\nclass Solution {\n    long res = 0L;\n    int MOD = (int)1e9 + 7;\n    int n;\n    Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();\n    Map<Integer, Integer> distanceToLastNode = new HashMap<>();\n    public int countRestrictedPaths(int n, int[][] edges) {\n        this.n = n;\n        for (int[] edge : edges) {\n            graph.computeIfAbsent(edge[0], value -> new HashMap<>()).put(edge[1], edge[2]);\n            graph.computeIfAbsent(edge[1], value -> new HashMap<>()).put(edge[0], edge[2]);\n        }\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);\n        pq.add(new int[] {0, n}); //{distance, city}\n        while (!pq.isEmpty()) {\n            int[] cur = pq.poll();\n            int city = cur[1], distance = cur[0];\n            if (!distanceToLastNode.containsKey(city)) distanceToLastNode.put(city, distance);\n            else if (distanceToLastNode.get(city) <= distance) continue;\n            Map<Integer, Integer> neighbors = graph.getOrDefault(city, new HashMap<>());\n                for (int nei : neighbors.keySet()) \n                    pq.add(new int[] {distance + neighbors.get(nei), nei}); \n        }\n        return dfs(1);\n    }\n    Map<Integer, Integer> memo = new HashMap<>();\n    private int dfs(int city) {\n        if (city == n) return 1;\n        if (memo.containsKey(city)) return memo.get(city);\n        Map<Integer, Integer> neighbors = graph.getOrDefault(city, new HashMap<>());\n        int count = 0;\n        for (int nei : neighbors.keySet())\n            if (distanceToLastNode.get(nei) < distanceToLastNode.get(city))\n                count = (count + dfs(nei)) % MOD;\n        memo.put(city, count);\n        return count;\n    }\n}\n```
[]