leetcode：787. K 站中转内最便宜的航班【k步最短路 + dfs记忆化 + defaultdict(dict)】

ac code

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # k站中转，可以走k + 1次
        connect = defaultdict(dict) # 二维dict
        for x, y, c in flights:
            connect[x][y] = c
        

        # 只能走k步的dfs
        # 自顶向下
        @cache
        def dfs(now, remain):
            # 成功退出
            if now == dst:
                return 0
            # 到达步数，无限远
            if remain == 0:
                return inf
            remain -= 1
            res = inf
            # 遍历下一个位置
            for nxt in connect[now]:
                res = min(res, dfs(nxt, remain) + connect[now][nxt])
            
            return res
        
        ans = dfs(src, k + 1)
        return ans if ans != inf else -1

分析

用一个defaultdict记录每一个点能飞到的地方和距离
自顶向下的dfs + cache
记忆化参数是当前的位置以及剩余的次数，结果是到达终点的距离
如果能到达终点，返回0
如果次数用尽，返回inf
次数-1，且当前res设置为inf
遍历所有能飞的下一个位置，然后res取res和dfs(nxt, remain) + connect[now][nxt]的最小值

这种思想就是把问题推到下一步，直到尽头（到达终点，次数用尽）

总结

dfs解决k步最短路问题，优雅