Solutions

# Bellman-Ford, relax edges level by level
# graphs

# Bellman-Ford, level by level relaxation - O(V + (E*k)) time, O(V) space
def findCheapestPrice(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): # NB: k+1 because k stops means k+1 flights
        newprices = prices.copy() # NB: use tmp array to avoid paths from same iteration to chain together and accidentally exceeed the stop limit

        for s, d, p in flights:
            if prices[s] == float("inf"):
                continue

            if prices[s] + p < newprices[d]:
                newprices[d] = prices[s] + p

        prices = newprices

    return prices[dst] if prices[dst] != float("inf") else -1


# Djikstra - O(E k log(Vk)) time, O(V k) space
def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    INF = float("inf")
    adj = [[] for _ in range(n)]
    dist = [[INF] * (k + 5) for _ in range(n)]
    for u, v, cst in flights:
        adj[u].append([v, cst])

    dist[src][0] = 0
    minHeap = [(0, src, -1)] # cost, node, stops
    while len(minHeap):
        cst, node, stops = heapq.heappop(minHeap)
        if dst == node: return cst
        if stops == k or dist[node][stops + 1] < cst:
            continue
        for nei, w in adj[node]:
            nextCst = cst + w
            nextStops = 1 + stops
            if dist[nei][nextStops + 1] > nextCst:
                dist[nei][nextStops + 1] = nextCst
                heapq.heappush(minHeap, (nextCst, nei, nextStops))

    return -1