787 Cheapest Flights Within K Stops

There arencities connected by mflights. Each fight starts from city uand arrives at vwith a pricew.

Now given all the cities and fights, together with starting citysrcand the destination dst, your task is to find the cheapest price fromsrctodstwith up tokstops. If there is no such route, output-1.

Example 1:

I
nput:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1

Output:
200

Explaination:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Example 2:

Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0

Output:
 500

Explanation:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Note:

• The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.

• The size of flights will be in range [0, n * (n - 1) / 2].

• The format of each flight will be (src, dst, price).

• The price of each flight will be in the range [1, 10000].

• k is in the range of [0, n - 1].

• There will not be any duplicated flights or self cycles.

Appoach 1: Brute Force (TLE)

The Idea: Search every possible path and check whether the current path has reached the destination, and return the minimum post path that also follows the constraints of the problem. We can make a few optimizations here like not checking paths that exceed size K in length, or not moving down paths that have accumulated a cost more than our current minimum cost.

Complexity: O(C(n,k)) time and O(k) space

from collections import defaultdict
import sys


class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """

        # create adj list graph
        g = defaultdict(list)
        for start, end, cost in flights:
            g[start].append((end, cost))

        min_cost = [sys.maxsize]
        def dfs(cur_stop, cur_node, cur_cost):
            if cur_stop <= K + 1 and cur_node == dst:
                min_cost[0] = min(min_cost[0], cur_cost)
            elif cur_stop <= K + 1 and cur_cost < min_cost[0]:
                for next_node, next_cost in g[cur_node]:
                    dfs(cur_stop + 1, next_node, cur_cost + next_cost)

        dfs(0, src, 0)
        return min_cost[0] if min_cost[0] != sys.maxsize else -1

Approach 2: PQ (TLE)

The Idea: Similar idea as before, but this time only take consider the current most minimum path that might reach the destination. There is still a possibility that all the paths have to be iterated through like before, but in the average case, this is a huge performance boost because the top of the heap that also contains the destination is guaranteed to be the minimum cost of all previous paths explored.

Complexity: O(log(C(n,k)) time

from collections import defaultdict
import heapq


class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """

        # create adj list graph
        g = defaultdict(list)
        for start, end, cost in flights:
            g[start].append((end, cost))

        heap = [(0, src, K + 1)]
        while heap:
            cur_cost, cur_node, cur_K = heapq.heappop(heap)
            if cur_node == dst:
                return cur_cost
            else if cur_K > 0:
                for next_node, next_cost in g[cur_node]:
                    heapq.heappush(heap, (cur_price + next_cost, next_node, cur_K - 1))
        return -1