There are n cities, numbered 0 to n - 1. Each entry flights[i] = [from, to, price] is a one-way flight from city from to city to that costs price.
You want to travel from city src to city dst, changing planes at most k times along the way. Every city you land in before dst counts as one stop, so a route of j flights makes j - 1 stops.
Return the lowest total price of such a route, or -1 if no route reaches dst within k stops.
0 → 2 → 3 → 4 costs only 60, but it stops at both 2 and 3, one stop too many. The best route with a single stop is 0 → 1 → 4, for 40 + 40 = 80.
Same flights, but two stops are now allowed, so 0 → 2 → 3 → 4 for 60 is fine. The route 0 → 1 → 2 → 3 → 4 would need three stops.
You can fly from 0 to 1, but the only flight touching city 2 goes from 2 to 1, the wrong way.
Constraints
2 <= n <= 1000 <= flights.length <= n * (n - 1) / 2flights[i].length == 30 <= from, to < n and from != to1 <= price <= 10⁴from and the same to. (A flight in each direction between two cities is allowed.)0 <= src, dst, k < nsrc != dstAn ordinary cheapest-path search can settle on a cheap route that uses too many stops, and then never reconsider a dearer route with fewer stops. Track the number of flights used as well as the price.
80