An Interest In:
Web News this Week
- April 2, 2024
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
September 10, 2022 06:20 am GMT
Original Link: https://dev.to/salahelhossiny/cheapest-flights-within-k-stops-428m
Cheapest Flights Within K Stops
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]
Original Link: https://dev.to/salahelhossiny/cheapest-flights-within-k-stops-428m
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To