Medium

Cheapest Flights Within K Stops

LAB

Given flights [from,to,price], return the cheapest price from src to dst using at most k stops, or -1 if unreachable.

EXAMPLES

Example 1

Input
{
  "n": 4,
  "flights": [
    [
      0,
      1,
      100
    ],
    [
      1,
      2,
      100
    ],
    [
      2,
      0,
      100
    ],
    [
      1,
      3,
      600
    ],
    [
      2,
      3,
      200
    ]
  ],
  "src": 0,
  "dst": 3,
  "k": 1
}

Output
700

FUNCTION SHAPE

n: intflights: intMatrixsrc: intdst: intk: int→int

SOLUTION NOTE

Pretty standard problem, we just need another dimension to our distance array to keep track of how many stops we have. Note that 'stops' in our array is actually the number of edges in the path. But the number of 'stop's' is the number of nodes in the path except the start and end, so it's actually the number of edges -1. This is why we need up to index k+2 in the array.

Compare this with the straightforward dp solution.

Reveal reference solution +

pythonREFERENCE

# Dijkstra with extra dimension
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, cost in flights:
        graph[u].append((v, cost))

    # dp[node][stops] = min cost to reach node with stops
    dp = [[float('inf')] * (k + 2) for _ in range(n)]
    dp[src][0] = 0

    # (cost, node, stops)
    heap = [(0, src, 0)]

    while heap:
        cost, node, stops = heapq.heappop(heap)

        if node == dst:
            return cost

        if stops > k:
            continue

        for nei, price in graph[node]:
            new_cost = cost + price
            if new_cost < dp[nei][stops + 1]:
                dp[nei][stops + 1] = new_cost
                heapq.heappush(heap, (new_cost, nei, stops + 1))

    return -1

# Alternative: DP solution
def findCheapestPrice(self, n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, cost in flights:
        graph[u].append((v, cost))

    @cache
    def dp(city, stops_remaining):
        if city == dst:
            return 0
        if stops_remaining < 0:
            return float('inf')

        min_cost = float('inf')
        for nei, price in graph[city]:
            min_cost = min(min_cost, price + dp(nei, stops_remaining - 1))
        return min_cost

    ans = dp(src, k)
    return -1 if ans == float('inf') else ans

TimeO(E * K * log(V * K))

SpaceO(V * K)

Open on LeetCode ↗