Cheapest Flights Within K Stops (Bellman–Ford)
Medium · Graphs · about 25 minutes
Asked at Airbnb, Uber, Google, Amazon, Booking.com.
n cities are linked by one-way flights flights[i] = [from, to, price]. Find the lowest total fare for getting from src to dst with no more than k stops in between (that is, at most k + 1 flights). Return -1 if there's no such itinerary.