发表于 2024.05.05

• 一开始使用了Dijkstra算法，后面发现不太适用，因为最多K次中转不代表最多K次循环。后面改用了队列+BFS的做法，队列维护节点、从源节点到该节点的路径总开销以及中转站数量，在每次循环中，从队列取出队首，更新节点的最小开销，如果该节点的中转站数量达到k后则不再进行松弛，否则松弛其后继节点并将松弛后的开销加入到队列中。由于一开始没考虑到稠密图的情况，因此可能会出现队列迅速膨胀导致MLE的问题，因此，如果循环中对应节点的开销大于当前的最小开销，则不再继续后面的松弛操作(如果没有负权, 后续的松弛操作是没意义的)。后面想了想，这不就是队列版本的Bellman-Ford算法嘛。

  from collections import deque
  
  
  class Solution:
      def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
          adj_list = [[] for _ in range(n)]  # type: List[List[Tuple[int, int]]]
          for u, v, cost in flights:
              adj_list[u].append((v, cost))
          dis = [-1] * n
          q = deque([(src, 0, -1)])
  
          while q:
              u, dis_cand, cnt = q.popleft()
              if dis[u] == -1 or dis[u] > dis_cand:
                  dis[u] = dis_cand
              else:
                  continue
              if cnt == k:
                  continue
              for v, cost in adj_list[u]:
                  q.append((v, dis_cand + cost, cnt + 1))
  
          return dis[dst]

• LC 题目链接