78. Cheapest Flights Within K Stops

Medium · Graph

There are n cities labelled 0 to n-1 connected by one-way flights, each with a price. Find the cheapest price to travel from a source city to a destination city using at most k intermediate stops.

The input is [n, flights, src, dst, k], where flights is a list of [from, to, price]. Return the cheapest total price, or -1 if the destination cannot be reached within k stops.

Examples

Example 1
Input: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1]
Output: 700
Explanation: Route 0 → 1 → 3 costs 700 and uses one stop.
Example 2
Input: [3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1]
Output: 200
Explanation: With one stop allowed, 0 → 1 → 2 costs 200, cheaper than the direct 500.

Constraints