Cheapest Flights Within K Stops
There are n cities numbered 0 to n - 1 and a list of one-way flights, where flights[i] = [from, to, price] is a flight from city from to city to costing price.
Given a start city src, a destination dst and an integer k, return the cheapest total price to fly from src to dst using at most k stops. A stop is a city where you change planes, so at most k stops means at most k + 1 flights. If no such route exists, return -1.
Constraints
1 <= n <= 1000 <= flights.length <= n · (n - 1)from !== to, and no two flights have the samefromandto1 <= price <= 10^40 <= src, dst, k < nandsrc !== dst
Examples
Example 1
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500],[1,3,600]], src = 0, dst = 3, k = 1 Output: 600
With at most 1 stop you may take 2 flights. 0 → 1 → 3 costs 700 and 0 → 2 → 3 costs 600. The 300 route 0 → 1 → 2 → 3 needs 2 stops, so it isn't allowed.
Example 2
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500],[1,3,600]], src = 0, dst = 3, k = 2 Output: 300
Same flights, but now 2 stops are allowed, so 0 → 1 → 2 → 3 for 300 is the cheapest.
Example 3
Input: n = 3, flights = [[0,1,50],[1,2,50],[0,2,300]], src = 0, dst = 2, k = 0 Output: 300
k = 0 allows direct flights only: 300.
JavaScript you'll use: Arrays: create, read, update Graphs and grids in JavaScript
/**
* @param {number} n
* @param {number[][]} flights
* @param {number} src
* @param {number} dst
* @param {number} k
* @return {number}
*/
function findCheapestPrice(n, flights, src, dst, k) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.