300. Cheapest Flights Within K Stops

MediumGraph

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. 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.

Examples

Input: 4 [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]] 0 3 1

Output: 700

Explanation: With at most 1 stop, the cheapest 0→3 route is 0→1→3 costing 700.

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
Loading...

Run checks all cases above. Submit evaluates all test cases.