LeetCode 787, 实在是不知道自己错在哪了，找不出逻辑错误了

第35个case实在是跑不过去，因为是一个极大的case，很难一个个debug了，裸改实在是看不出自己的code逻辑错在哪了，求各位大佬帮帮忙！

以下是code（python）：
class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dic = {}
        self.res = float("Inf")
        for i in flights:                               #用dict建图
            if i[0] not in dic:
                dic[i[0]] = [(i[1],i[2])]
            else:
                dic[i[0]].append((i[1],i[2]))
        k+=1
        visited = {}
        def dfs(now,stop,price):                                  #dfs找出所有路径
            if stop<=k and now == dst:                       #如果路径存在且停留数合乎要求，则保留最小price
                self.res = min(self.res,price)
                return
            if stop>=k:                                                  #如果停留数不合要求，直接终止
                return
            visited[now] = stop                                     #用一个dict去记录走过的路径，防止重复
            if now in dic:
                for i in dic[now]:
                    if i[0] not in visited or stop < visited[i[0]]:                   #如果下一步不在dict里面，或者停留数小于原本在dic里面的这一步，则能够递归，否则不重复路径
                        if i[0] in visited:
                            visited[i[0]] = stop                                               #如果下一步在dict里面，更新停留数
                        dfs(i[0],stop+1,price+i[1])
        dfs(src,0,0)
        return self.res if self.res!=float('Inf') else -1

“停留数小于原本在dic里面的这一步则能够递归”不对啊
假设src=1 dst=4
1可以到3，
1也可以到2,2可以到3
3可以到4
如果price1到2 + price2到3 < price1到3，然后你的算法先算了1到3，那就不会再算1到2接2到3这条路了

我以为这题应该用dijkstra呢？

anhpp 发表于 2019-12-19 12:14
我以为这题应该用dijkstra呢？

老哥，这道题是应该用dij，只是我当时第一个想到的就是dfs哈哈

一剑终情 发表于 2019-12-19 10:59
“停留数小于原本在dic里面的这一步则能够递归”不对啊
假设src=1 dst=4
1可以到3，

有道理老哥，我等会就去改改，应该在完成步骤后remove掉visit里面的path值

wowowonini 发表于 2019-12-19 12:27
老哥，这道题是应该用dij，只是我当时第一个想到的就是dfs哈哈

哈哈哈 有最小距离 最小代价的 没办法啊
标准的单源最短路径啊 single source shortest path