Cheapest Flights Within K Stops in Java

You get n cities, numbered from 0 to n - 1. You also get an array flights. Each flight is [from, to, price]. It goes one way, from city from to city to, and costs price.

You also get a start city src, an end city dst and a number k. Return the lowest total price to get from src to dst. The trip may make at most k stops. Return -1 if no such trip exists.

A stop is a city where you change planes. So a trip with k stops takes k + 1 flights. If src and dst are the same city, the answer is 0.

Example 1:

Input: n = 5,
flights = [
  [0, 1, 40], [1, 2, 40], [2, 4, 40],
  [0, 3, 150], [3, 4, 30], [1, 4, 200]
],
src = 0, dst = 4, k = 1
Output: 180
Explanation: With at most 1 stop, two trips reach city 4:
0 → 1 → 4 costs 40 + 200 = 240,
0 → 3 → 4 costs 150 + 30 = 180.
The trip 0 → 1 → 2 → 4 costs only 120, but it makes 2 stops.

Example 2:

Input: n = 5,
flights = [
  [0, 1, 40], [1, 2, 40], [2, 4, 40],
  [0, 3, 150], [3, 4, 30], [1, 4, 200]
],
src = 0, dst = 4, k = 2
Output: 120
Explanation: These are the same flights, but now 2 stops are allowed.
So the trip 0 → 1 → 2 → 4 counts.
It costs 40 + 40 + 40 = 120.

Example 3:

Input: n = 4,
flights = [
  [0, 1, 30], [1, 2, 30], [3, 2, 30]
],
src = 0, dst = 3, k = 2
Output: -1
Explanation: No flight lands in city 3.
The flight [3, 2] goes from city 3 to city 2, not back.
So no trip reaches city 3.

Constraints:

• 1 to 100 cities.
• 0 to n · (n - 1) / 2 flights.
• Each flight joins two different cities.
• No two flights have the same from and the same to.
• Each price is a whole number from 1 to 10,000.
• src, dst and k are each from 0 to n - 1.