leetcode：787. The cheapest transfer flight in station K [k-step shortest path + DFS memory + defaultdict (dict)]

ac code

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # k Transfer station , You can go k + 1 Time 
        connect = defaultdict(dict) #  A two-dimensional dict
        for x, y, c in flights:
            connect[x][y] = c
        

        #  Can only go k Step by step dfs
        #  The top-down 
        @cache
        def dfs(now, remain):
            #  Quit successfully 
            if now == dst:
                return 0
            #  Arrival steps , infinity 
            if remain == 0:
                return inf
            remain -= 1
            res = inf
            #  Traverse the next position 
            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

analysis

Use one defaultdict Record where and how far each point can fly
Top down dfs + cache
The memory parameters are the current position and the number of times remaining , The result is the distance to the destination
If we can reach the end , return 0
If you run out of times , return inf
frequency -1, And the current res Set to inf
Traverse all the next positions that can fly , then res take res and dfs(nxt, remain) + connect[now][nxt] The minimum value of

This idea is to push the problem to the next step , To the end （ Reach the end point , Run out of times ）

summary

dfs solve k Step shortest path problem , grace