Cheapest Flights
Within K Stops

Problem Statement

You are given information about n cities connected by m flights. Each flight is represented as [fromi, toi, pricei] indicating a direct flight from city fromi to city toi with a cost of pricei.

You are also given three integers:

• src – the starting city
• dst – the target city
• k – the maximum number of allowed stops (i.e., you can take at most k + 1 flights)

Your goal is to find the cheapest price to travel from src to dst with at most k stops. If such a route doesn't exist, return -1.

Algorithm Steps

1. Build an adjacency list to represent the graph of cities and flights.
2. Initialize a queue with a tuple (src, 0, 0) representing (current city, cost so far, stops so far).
3. Maintain a minCost map to record the minimum cost to reach a node with a certain number of stops.
4. While the queue is not empty:
1. Dequeue a tuple (city, cost, stops).
2. If city == dst, update the result if cost is lower.
3. If stops > k, continue to next iteration.
4. For each neighbor of the current city, push (neighbor, cost + price, stops + 1) to the queue if this new cost is cheaper than any previously recorded cost to that neighbor with same or fewer stops.
5. If a path is found, return the cheapest cost; otherwise, return -1.

Code

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

  const queue = [[src, 0, 0]]; // [city, cost, stops]
  const minCost = Array.from({ length: n }, () => Array(k + 2).fill(Infinity));
  minCost[src][0] = 0;

  while (queue.length) {
    const [city, cost, stops] = queue.shift();
    if (stops > k) continue;
    const neighbors = adj.get(city) || [];
    for (const [next, price] of neighbors) {
      const newCost = cost + price;
      if (newCost < minCost[next][stops + 1]) {
        minCost[next][stops + 1] = newCost;
        queue.push([next, newCost, stops + 1]);
      }
    }
  }

  const result = Math.min(...minCost[dst]);
  return result === Infinity ? -1 : result;
}

console.log(findCheapestPrice(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 1)); // 500
console.log(findCheapestPrice(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 2)); // 300