| 1 | class Solution { |
| 2 | public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { |
| 3 | Map<Integer, List<int[]>> adj = new HashMap<>(); |
| 4 | for (int[] i : flights) |
| 5 | adj.computeIfAbsent(i[0], value -> new ArrayList<>()).add(new int[] { i[1], i[2] }); |
| 6 | |
| 7 | int[] stops = new int[n]; |
| 8 | Arrays.fill(stops, Integer.MAX_VALUE); |
| 9 | PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); |
| 10 | // {dist_from_src_node, node, number_of_stops_from_src_node} |
| 11 | pq.offer(new int[] { 0, src, 0 }); |
| 12 | |
| 13 | while (!pq.isEmpty()) { |
| 14 | int[] temp = pq.poll(); |
| 15 | int dist = temp[0]; |
| 16 | int node = temp[1]; |
| 17 | int steps = temp[2]; |
| 18 | if (steps > stops[node] || steps > k + 1) |
| 19 | continue; |
| 20 | stops[node] = steps; |
| 21 | if (node == dst) |
| 22 | return dist; |
| 23 | if (!adj.containsKey(node)) |
| 24 | continue; |
| 25 | for (int[] a : adj.get(node)) { |
| 26 | pq.offer(new int[] { dist + a[1], a[0], steps + 1 }); |
| 27 | } |
| 28 | } |
| 29 | return -1; |
| 30 | } |
| 31 | } |