There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
prices = [float("inf")] * n
prices[src] = 0
for i in range(k + 1):
tmpPrices = prices.copy()
for s, d, p in flights: # s=source, d=dest, p=price
if prices[s] == float("inf"):
continue
if prices[s] + p < tmpPrices[d]:
tmpPrices[d] = prices[s] + p
prices = tmpPrices
return -1 if prices[dst] == float("inf") else prices[dst]
Top comments (1)
Last minute flights refer to flights that are booked very close to the date of travel, usually within a week or even a few days before departure. These flights are often more expensive than those booked in advance, as airlines raise their prices to capitalize on the urgency of last-minute travelers.