Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
September 10, 2022 06:20 am GMT

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:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To