Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumshortest-path-weighted

Cheapest Flights Within K Stops

Problem (restated)

n cities and directed flights [from, to, price]. Return the cheapest price from src to dst using at most k stops (so at most k+1 flights). -1 if impossible.

Intuition

A cheaper path may use more stops than a budget allows, so plain Dijkstra (first pop is cheapest, any hop count) is wrong. Either relax every edge k+1 times (Bellman-Ford, one extra hop per round) or put stops in the Dijkstra state.

Approaches

Bellman-Ford k+1 rounds

Unverified

Time O(k·E)Space O(n)

Idea. dist[src] = 0. For k+1 rounds, copy dist into nxt and relax every flight against the previous round so each round adds at most one hop. Answer dist[dst].

Walkthrough. src=0, dst=2, k=1, flights 0→1 (100), 1→2 (100), 0→2 (500). After 1 hop: 500 via the direct. After 2 hops: 200 via 0-1-2.

Trade-offs. Simple, no heap. Must copy dist each round or you leak extra hops. k = 0 is a single round.

Solution

export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  let dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= k; i++) {
    const nxt = dist.slice();
    for (const [u, v, w] of flights) {
      if (dist[u]! + w < nxt[v]!) nxt[v] = dist[u]! + w;
    }
    dist = nxt;
  }
  return dist[dst] === Infinity ? -1 : dist[dst]!;
}

export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  let dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= k; i++) {
    const nxt = dist.slice();
    for (const [u, v, w] of flights) {
      if (dist[u]! + w < nxt[v]!) nxt[v] = dist[u]! + w;
    }
    dist = nxt;
  }
  return dist[dst] === Infinity ? -1 : dist[dst]!;
}

Dijkstra with stop state

Unverified

Time O(k·E log (k n))Space O(k n)

Idea. Heap of (cost, node, edgesUsed). best[v][edges] is the cheapest to v with that hop count. First time dst is popped, that cost is optimal. Stop expanding at k+1 edges.

Walkthrough. Same graph. The 500 direct is popped first for dst with 1 edge, but we only return on pop — the 200 with 2 edges is cheaper and is popped first overall because 200 < 500.

Trade-offs. Needed when you think in Dijkstra. Do not finalize a node on first visit: a costlier route with fewer hops can still win later.

Solution

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, edgesUsed) so a cheaper-with-more-stops path
 * cannot hide a costlier-with-fewer-stops path that still reaches dst.
 */
export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of flights) adj[u]!.push([v, w]);
  const best = Array.from({ length: n }, () => new Array<number>(k + 2).fill(Infinity));
  best[src]![0] = 0;
  const pq: [number, number, number][] = [[0, src, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [cost, u, edges] = pq.shift()!;
    if (u === dst) return cost;
    if (edges === k + 1) continue;
    for (const [v, w] of adj[u]!) {
      const nc = cost + w;
      if (nc < best[v]![edges + 1]!) {
        best[v]![edges + 1] = nc;
        pq.push([nc, v, edges + 1]);
      }
    }
  }
  return -1;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, edgesUsed) so a cheaper-with-more-stops path
 * cannot hide a costlier-with-fewer-stops path that still reaches dst.
 */
export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of flights) adj[u]!.push([v, w]);
  const best = Array.from({ length: n }, () => new Array<number>(k + 2).fill(Infinity));
  best[src]![0] = 0;
  const pq: [number, number, number][] = [[0, src, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [cost, u, edges] = pq.shift()!;
    if (u === dst) return cost;
    if (edges === k + 1) continue;
    for (const [v, w] of adj[u]!) {
      const nc = cost + w;
      if (nc < best[v]![edges + 1]!) {
        best[v]![edges + 1] = nc;
        pq.push([nc, v, edges + 1]);
      }
    }
  }
  return -1;
}

Template connection

Dijkstra + extra state (stops), or Bellman-Ford bounded by path length. Same “extend the state, not the algorithm” move as LC 2093 (discounts).

Reflection

At most k stops means k + 1 edges. Each round relaxes from a copy of the previous round. Relaxing inside the same round counts extra edges.
Dijkstra with a (node, stops used) state returns the same answer. Unreachable is −1.
k = 0 allows only a direct flight. Prices are positive. The hop limit is what cuts a cycle.