Cheapest Flights Within K Stops Medium 0 attempts
LeetCode ↗

Cheapest Flights Within K Stops

Medium GraphBFSDFS LeetCode

There's a flight network of n cities connected by one-way flights, where each entry in flights is [from, to, price]. Starting at city src, find the lowest total price to reach city dst while making at most k stops along the way, and return that price. A stop is an intermediate city, so at most k + 1 flight edges are allowed. Return -1 when no qualifying route exists.

Input Format
Implement findCheapestPrice(n, flights, src, dst, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

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

Example 3

Input
n = 3
flights = [[0,1,10]]
src = 0
dst = 2
k = 1
Output
-1
Constraints
  • 1 <= n <= 100
  • 0 <= flights.length <= n*(n-1)/2
  • 0 <= src, dst, k < n
  • 1 <= price <= 10^4
Test Cases (3)
Case 1
Args: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1] Expected: 700
Case 2
Args: [3,[[0,1,10],[1,2,10],[0,2,100]],0,2,0] Expected: 100
Case 3
Args: [3,[[0,1,10]],0,2,1] Expected: -1
Topics
GraphBFSDFS

Bellman-Ford (K+1 iterations)

Relax edges K+1 times to find shortest path with at most K stops.

javascript
function findCheapestPrice(n, flights, src, dst, k) {
  let prices = Array(n).fill(Infinity);
  prices[src] = 0;
  for (let i = 0; i <= k; i++) {
    const temp = [...prices];
    for (const [u, v, w] of flights) {
      if (prices[u] !== Infinity) temp[v] = Math.min(temp[v], prices[u] + w);
    }
    prices = temp;
  }
  return prices[dst] === Infinity ? -1 : prices[dst];
}

Time: O(k * E) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript