787. Cheapest Flights Within K Stops

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

solution

• Dijkstra

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(dict)
        pq = [(0, src, 0)]

        for u, v, w in flights:
            graph[u][v] = w
        
        while pq:
            total, src, stops = heapq.heappop(pq)
            if src == dst:
                return total
            if stops > k:
                continue
            for dest, cost in graph[src].items():
                heapq.heappush(pq, (total + cost, dest, stops + 1))
        return -1

时间复杂度：O() 空间复杂度：O()

• bfs

  • 如果没有边的权重，那么就是bfs的最短路径问题。有了权重以后，该如何选择？ collections.defaultdict(dict)

  • 剪枝

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(dict)
        for u, v, w in flights:
            graph[u][v] = w
        
        queue = collections.deque([(src, 0)])
        step = 0
        res = float('inf')
        while queue:
            for _ in range(len(queue)):
                cur, cost = queue.popleft()
                if cur == dst:
                    res = min(res, cost)
                    continue

                for v, w in graph[cur].items():
                    if cost + w > res:
                        continue
                    queue.append([v, cost+w])
            if step > k:
                break
            step += 1
        return -1 if res == float('inf') else res        

时间复杂度：O(E*K) 空间复杂度：O()

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in flights:
            graph[u].append([v, w])
        
        queue = collections.deque([(src, 0, 0)])
        res = float('inf')
        while queue:            
            cur, visited, cost = queue.popleft()            
            
            if cost <= res and visited <= k and cur != dst:
                for v, w in graph[cur]:                   
                    queue.append([v, visited + 1, cost + w])
            
            if cur == dst:
                res = min(res, cost)
                continue
            
        return -1 if res == float('inf') else res