Cheapest Flights Within K Stops

Examples

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700

With at most 1 stop, the cheapest route is 0 -> 1 -> 3, costing 100 + 600 = 700. The route 0 -> 1 -> 2 -> 3 is cheaper (300) but uses 2 stops, more than k allows.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200

With at most 1 stop, 0 -> 1 -> 2 costs 100 + 100 = 200, cheaper than the direct flight 0 -> 2 at 500.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500

With 0 stops allowed, only the direct flight 0 -> 2 is usable, costing 500.

Constraints

• 1 <= n <= 100

• 0 <= flights.length <= (n * (n - 1) / 2)

• flights[i] = [from, to, price] with from != to and 1 <= price <= 10^4

• 0 <= src, dst, k < n

• There are no duplicate flights.

Approach

This looks like a shortest-path problem, but with a hard limit on the number of edges used, which plain Dijkstra's algorithm doesn't naturally track (it would happily lock in a cheap path that uses too many stops, and never revisit that city with a more-expensive-but- within-limit path).

The clean fix is a Bellman-Ford style relaxation, run for exactly k + 1 rounds (since at most k stops means at most k + 1 flights). In each round, relax every flight - try updating the destination's price using the source's price from the end of the previous round. Using last round's snapshot (rather than letting updates chain within the same round) is what correctly limits each round to adding exactly one more flight to any path.

A closely related alternative is a modified Dijkstra / BFS where each queue entry tracks both a city and how many flights have been used to reach it so far, expanding stop-by-stop (a "leveled" BFS) rather than strictly by cheapest-cost-first.

Solutions

Optimal - Bellman-Ford Style Relaxation

Track the cheapest known price to reach every city, starting at 0 for src and infinity elsewhere. Run exactly k + 1 rounds. In each round, take a fresh copy of the current prices, and for every flight [from, to, price], check whether last round's price at from plus this flight's price improves the new copy's price at to. After the round, replace the working prices with the new copy. Using a fresh copy each round guarantees a round only ever adds exactly one more flight to any path, which is exactly what keeps the stop count bounded by the number of rounds.

function findCheapestPrice(n, flights, src, dst, k) {
  let prices = new Array(n).fill(Infinity);
  prices[src] = 0;

  for (let round = 0; round < k + 1; round++) {
    const nextPrices = prices.slice();

    for (const [from, to, price] of flights) {
      if (prices[from] === Infinity) continue;
      const candidate = prices[from] + price;
      if (candidate < nextPrices[to]) {
        nextPrices[to] = candidate;
      }
    }

    prices = nextPrices;
  }

  return prices[dst] === Infinity ? -1 : prices[dst];
}

Time: O(k * E), where E is the number of flights, since each of the k + 1 rounds relaxes every flight once · Space: O(n) for the two price arrays

Modified Dijkstra with Stops Tracked in State

Use a min-heap of [cost, city, stopsUsed], starting from [0, src, 0]. Repeatedly pop the cheapest entry; if it's the destination, that cost is the answer (Dijkstra's ordering still guarantees it's cheapest among states popped so far). Otherwise, if stopsUsed <= k, push a new entry for every outgoing flight, with one more stop used. To avoid wasted work, skip expanding a city again once it's been reached with an equal-or-fewer stop count at an equal-or- lower cost previously - but never prune purely on cost the way plain Dijkstra would, since a more expensive route with more remaining stops budget can still turn out to matter.

function findCheapestPrice(n, flights, src, dst, k) {
  const graph = new Map();
  for (const [from, to, price] of flights) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from).push([to, price]);
  }

  // Best stops used to reach a city at-or-below a given cost; used only
  // to skip strictly-dominated states, never to prune by cost alone.
  const bestStopsAtCity = new Array(n).fill(Infinity);

  const heap = [[0, src, 0]];
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
        if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
        if (smallest === i) break;
        [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }

  while (heap.length > 0) {
    const [cost, city, stopsUsed] = pop();
    if (city === dst) return cost;
    if (stopsUsed > k || stopsUsed >= bestStopsAtCity[city]) continue;
    bestStopsAtCity[city] = stopsUsed;

    const neighbors = graph.get(city) || [];
    for (const [next, price] of neighbors) {
      push([cost + price, next, stopsUsed + 1]);
    }
  }

  return -1;
}

Time: O(E * k * log(E * k)) in the worst case, since a city can be re-expanded up to k times and each push/pop is logarithmic in heap size · Space: O(n + E * k) for the graph and the heap, which can hold multiple entries per city