#787

Cheapest Flights Within K Stops

medium· Advanced Graphsruns: 0

There are n cities connected by some flights. You are given flights where flights[i] = [from, to, price]. 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.

wpm 0acc 100%time 0:000 / 580

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 _ in range(k + 1):
            tmp = prices[:]
            for u, v, w in flights:
                if prices[u] == float("inf"):
                    continue
                if prices[u] + w < tmp[v]:
                    tmp[v] = prices[u] + w
            prices = tmp
        return prices[dst] if prices[dst] != float("inf") else -1

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.