This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by SalahElhossiny
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]
This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by SalahElhossiny
SalahElhossiny | Sciencx (2022-09-10T06:20:33+00:00) Cheapest Flights Within K Stops. Retrieved from https://www.scien.cx/2022/09/10/cheapest-flights-within-k-stops/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.