Cheapest Flights Within K Stops

Medium~30 min

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from, to, price] represents a flight from city from to city to with cost price.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

A stop is an intermediate city along the path (not including src or dst).

Examples

Example 1
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
Explanation: The optimal path with at most 1 stop is 0 -> 1 -> 3 with cost 100 + 600 = 700. The path 0 -> 1 -> 2 -> 3 costs 400 but uses 2 stops.
Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The cheapest path with at most 1 stop is 0 -> 1 -> 2 with cost 100 + 100 = 200.
Example 3
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With 0 stops allowed, only direct flights are valid. The direct flight 0 -> 2 costs 500.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= n * (n - 1) / 2
  • flights[i].length == 3
  • 0 <= from_i, to_i < n
  • from_i != to_i
  • 1 <= price_i <= 10^4
  • 0 <= src, dst, k < n
  • src != dst
  • Expected time complexity: O(V + E × K)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run