## DEV Community 👩‍💻👨‍💻 is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

SalahElhossiny

Posted on

# 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]

``````