Cheapest Flights Within K Stops

Problem

https://leetcode.com/problems/cheapest-flights-within-k-stops/

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from:sub:`i`, to:sub:`i`, price:sub:`i`] indicates that there is a flight from city from:sub:`i` to city to:sub:`i` with cost price:sub:`i`.

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.

Example 1:

image1

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
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

image2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

image3

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

  • 2 <= n <= 100

  • 0 <= flights.length <= (n * (n - 1) / 2)

  • flights[i].length == 3

  • 0 <= from:sub:`i`, to:sub:`i`< n

  • from:sub:`i`!= to:sub:`i`

  • 1 <= price:sub:`i`<= 10:sup:`4`

  • There will not be any multiple flights between two cities.

  • 0 <= src, dst, k < n

  • src != dst

Pattern

Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue)

Approaches

Code

import heapq
from collections import defaultdict


def findCheapestPrice(
    n: int,
    flights: list[list[int]],
    src: int,
    dst: int,
    k: int,
) -> int:
    graph = defaultdict(list)
    for [u, v, price] in flights:
        graph[u].append((v, price))

    dist = [[float("inf")] * (k + 2) for _ in range(n)]

    min_heap = [(0, src, 0)]
    while min_heap:
        price, u, stops = heapq.heappop(min_heap)

        if dst == u:
            return price

        if stops > k or dist[u][stops] < price:
            continue

        if price > dist[u][stops]:
            continue

        for v, w in graph[u]:
            next_price = w + price
            if dist[v][stops + 1] > next_price:
                dist[v][stops + 1] = next_price
                heapq.heappush(min_heap, (next_price, v, stops + 1))

    return -1

Test

>>> from cheapest_flights_within_k_stops__modified_dijkstra import findCheapestPrice
>>> findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1)
700
>>> findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)
200
>>> findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0)
500
cheapest_flights_within_k_stops__modified_dijkstra.findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) → int