Cheapest Flights Within K Stops solution and explanation

from collections import deque, defaultdict

def find_cheapest_price(n, flights, src, dst, k):
    adj_list = defaultdict(list)
    for start, end, price in flights:
        adj_list[start].append((end, price))
    
    # (current city, current cost, remaining stops)
    queue = deque([(src, 0, k + 1)])
    
    min_cost = float('inf')
    
    while queue:
        position, cost, stops = queue.popleft()
        if position == dst:
            min_cost = min(min_cost, cost)
            continue
        if stops > 0:
            for neighbor, price in adj_list[position]:
                if cost + price < min_cost:
                    queue.append((neighbor, cost + price, stops - 1))
    return min_cost if min_cost != float('inf') else -1

function findCheapestPrice(n, flights, src, dst, k) {
    const adjList = {};
    flights.forEach(([start, end, price]) => {
        if (!adjList[start]) adjList[start] = [];
        adjList[start].push([end, price]);
    });
    
    const queue = [[src, 0, k + 1]];
    let minCost = Infinity;
    
    while (queue.length > 0) {
        const [city, cost, stops] = queue.shift();
        if (city === dst) {
            minCost = Math.min(minCost, cost);
            continue;
        }
        if (stops > 0) {
            (adjList[city] || []).forEach(([nextCity, price]) => {
                if (cost + price < minCost) {
                    queue.push([nextCity, cost + price, stops - 1]);
                }
            });
        }
    }
    return minCost === Infinity ? -1 : minCost;
}

import java.util.*;

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] f : flights) {
            adj.computeIfAbsent(f[0], x -> new ArrayList<>()).add(new int[]{f[1], f[2]});
        }
        
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.add(new int[]{0, src, k + 1});
        
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int cost = top[0], city = top[1], stops = top[2];
            if (city == dst) return cost;
            if (stops > 0) {
                for (int[] next : adj.getOrDefault(city, Collections.emptyList())) {
                    heap.add(new int[]{cost + next[1], next[0], stops - 1});
                }
            }
        }
        return -1;
    }
}

#include <queue>
#include <vector>
#include <unordered_map>
#include <limits.h>

using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    unordered_map<int, vector<pair<int, int>>> adj;
    for (auto f : flights) {
        adj[f[0]].push_back({f[1], f[2]});
    }
    
    typedef tuple<int, int, int> T;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({0, src, k+1});
    
    while (!pq.empty()) {
        auto [cost, city, stops] = pq.top(); pq.pop();
        if (city == dst) return cost;
        if (stops > 0) {
            for (auto& [nextCity, price] : adj[city]) {
                pq.push({cost + price, nextCity, stops - 1});
            }
        }
    }
    return -1;
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	const inf = 0x3f3f3f3f
	dist := make([]int, n)
	backup := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	dist[src] = 0
	for i := 0; i < k+1; i++ {
		copy(backup, dist)
		for _, e := range flights {
			f, t, p := e[0], e[1], e[2]
			dist[t] = min(dist[t], backup[f]+p)
		}
	}
	if dist[dst] == inf {
		return -1
	}
	return dist[dst]
}