787. Cheapest Flights Within K Stops

Description

image-20210825133449042

image-20210825133512600

Solution

BFS+cost[] array

Ignore the vertex with more step && more cost, just to prune

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adjacent = defaultdict(list)
        cost = [sys.maxsize] * n
        queue = [src]
        cost[src] = 0
        step = 0
        for f in flights:
            adjacent[f[0]].append((f[1],f[2]))
        while len(queue) > 0 and step <= k:
            size = len(queue)
            tmp = cost.copy()
            for i in range(size):
                top = queue[0]
                queue.pop(0)
                for (v,e) in adjacent[top]:
                    if(cost[top] + e < tmp[v]):
                        queue.append(v)
                        tmp[v] = cost[top] + e
            for i in range(len(cost)):
                cost[i] = tmp[i]
            step += 1
        return -1 if cost[dst] is sys.maxsize else cost[dst]