Almost Same problem as 787. Cheapest Flights Within K Stops
Using two arrays (minCost and minTime) to do relaxation in Dijkstra search\n\n787. Cheapest Flights Within K Stops\n\n    public int findCheapestPrice(int n, in
Using two arrays (minCost and minTime) to do relaxation in Dijkstra search\n\n787. Cheapest Flights Within K Stops\n```\n    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {\n        HashMap<Integer, Integer>[] graph = new HashMap[n];\n        for (int i = 0; i < n; i++)\n            graph[i] = new HashMap<>();\n        for (int[] flight : flights)\n            graph[flight[0]].put(flight[1], flight[2]);\n\n        int[] minCosts = new int[n], minStops = new int[n];\n        Arrays.fill(minCosts, Integer.MAX_VALUE);\n        Arrays.fill(minStops, Integer.MAX_VALUE);\n        minCosts[src] = 0;\n        minStops[src] = 0;\n\n        // The priority queue would contain (node, cost, stops)\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);\n        pq.offer(new int[]{src, 0, 0});\n\n        while (!pq.isEmpty()) {\n            int[] info = pq.poll();\n            int node = info[0], costs = info[1], stops = info[2];\n\n            if (node == dst) return costs;\n\n            for (int nextNode : graph[node].keySet()) {\n                int price = graph[node].get(nextNode);\n                if (stops > k) continue;\n                if (costs + price < minCosts[nextNode]) {\n                    pq.offer(new int[]{nextNode, costs + price, stops + 1});\n                    minCosts[nextNode] = costs + price;\n                    minStops[nextNode] = stops + 1;\n                } else if (stops + 1 < minStops[nextNode]) {\n                    pq.offer(new int[]{nextNode, costs + price, stops + 1});\n                    minStops[nextNode] = stops + 1;\n                }\n            }\n        }\n\n        return -1;\n    }\n```\n\n\n1928. Minimum Cost to Reach Destination in Time\n```\n    public int minCost(int maxTime, int[][] edges, int[] passingFees) {\n        int n = passingFees.length;\n        int[] minTime = new int[n];\n        int[] minCosts = new int[n];\n        Arrays.fill(minTime, Integer.MAX_VALUE);\n        Arrays.fill(minCosts, Integer.MAX_VALUE);\n        minTime[0] = 0;\n        minCosts[0] = passingFees[0];\n\n        HashMap<Integer, Integer>[] graph = new HashMap[n];\n        for (int i = 0; i < n; i++)\n            graph[i] = new HashMap<>();\n        for (int[] e : edges) {\n            if (!graph[e[0]].containsKey(e[1]) || graph[e[0]].get(e[1]) > e[2])\n                graph[e[0]].put(e[1], e[2]);\n            if (!graph[e[1]].containsKey(e[0]) || graph[e[1]].get(e[0]) > e[2])\n                graph[e[1]].put(e[0], e[2]);\n        }\n\n        // The priority queue would contain (node, cost, time)\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);\n        pq.offer(new int[]{0, passingFees[0], 0});\n\n        while (!pq.isEmpty()) {\n            int[] info = pq.poll();\n            int node = info[0], costs = info[1], time = info[2];\n            if (node == n - 1) return costs;\n\n            for (int nextNode : graph[node].keySet()) {\n                int passingTime = graph[node].get(nextNode);\n                int newFee = passingFees[nextNode];\n                if (time + passingTime > maxTime) continue;\n\n                if (costs + newFee < minCosts[nextNode]) {\n                    pq.offer(new int[]{nextNode, costs + newFee, time + passingTime});\n                    minCosts[nextNode] = costs + newFee;\n                    minTime[nextNode] = time + passingTime;\n                } else if (time + passingTime < minTime[nextNode]) {\n                    pq.offer(new int[]{nextNode, costs + newFee, time + passingTime});\n                    minTime[nextNode] = time + passingTime;\n                }\n            }\n        }\n\n        return -1;\n    }\n```
[]