Cheapest Trip with Few Stops

You are flying from city start to city end. flights lists the one-way flights on offer: [a, b, price] flies from a to b for price euros. You are happy to change planes, but you will land in at most max_stops cities on the way (not counting start and end), so the trip uses at most max_stops + 1 flights.

Write cheapest_trip(flights, start, end, max_stops) that returns the lowest total price of such a trip, or -1 if there is none. start and end are different cities.

Examples

flights = [
    ['LIS', 'MAD', 100], ['MAD', 'ROM', 100], ['LIS', 'ROM', 500],
    ['ROM', 'ATH', 100], ['MAD', 'ATH', 600],
]
cheapest_trip(flights, 'LIS', 'ROM', 1)  # returns 200
cheapest_trip(flights, 'LIS', 'ROM', 0)  # returns 500
cheapest_trip(flights, 'LIS', 'ATH', 1)  # returns 600
cheapest_trip(flights, 'LIS', 'ATH', 2)  # returns 300

With one stop, Athens can be reached through Madrid (100 + 600) or through Rome (500 + 100), so the best price is 600. With two stops, Lisbon to Madrid to Rome to Athens costs 300.

Constraints

• Up to 100 cities and 2,000 flights. Prices are integers from 1 to 10,000.
• 0 <= max_stops < 100.
• Flights can form loops, and there can be several flights between the same two cities.