# 787 Cheapest Flights Within K Stops

There are`n`cities connected by `m`flights. Each fight starts from city `u`and arrives at `v`with a price`w`.

Now given all the cities and fights, together with starting city`src`and the destination `dst`, your task is to find the cheapest price from`src`to`dst`with up to`k`stops. 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:

``````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
"""

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
"""

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``````

Last updated