787. Cheapest Flights Within K Stops

There are n cities and flights[i] = [from, to, price]. Return the cheapest price from src to dst using at most k stops (k + 1 flights), or -1 if there is no such route.

Expand level by level, where level = flights taken. Keep the best known price per city and only re-queue a city when this level reaches it more cheaply. Stop after k + 1 levels.

1function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
2  const adj: [number, number][][] = Array.from({ length: n }, () => []);
3  for (const [u, v, w] of flights) adj[u].push([v, w]);
4  const best = new Array(n).fill(Infinity);
5  best[src] = 0;
6  let level: [number, number][] = [[src, 0]];
7  for (let stops = 0; stops <= k && level.length; stops++) {
8    const next: [number, number][] = [];
9    for (const [u, cost] of level)
10      for (const [v, w] of adj[u])
11        if (cost + w < best[v]) { best[v] = cost + w; next.push([v, cost + w]); }
12    level = next;
13  }
14  return best[dst] === Infinity ? -1 : best[dst];
15}

flights

best

∞

current level (city, cost)

0, 0

Start at 0 with cost 0.

1 / 0

Space: play/pause · ←/→: step