787. K 站中转内最便宜的航班

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 toi 抵达 pricei。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
航班没有重复，且不存在自环
0 <= src, dst, k < n
src != dst

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

import sys
import time
from typing import List


class Solution:
    from functools import lru_cache
    def __init__(self):
        import sys
        self.GET_RES = False

    @lru_cache(None)
    def dfs(self, now, step, price):
        # print(f'now:{now}, step:{step}, price:{price}, GET_RES:{self.GET_RES}')
        if ((step > self.k and now != self.dst) or  # k步还没到终点 结束
                (price >= self.min_price) or  # 已经超过最小花费了 放弃这条路
                (price >= self.min_prices[now] and self.GET_RES)):  # 之前已经到过这里，并且花费更少，注意可能上次到这里花费更少却到不了终点
            return
        self.min_prices[now] = price
        if now == self.dst:
            self.GET_RES = True
            self.min_price = min(self.min_price, price)
        else:
            for next, cost in self.route[now]:
                self.dfs(next, step + 1, price + cost)

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        self.min_price = sys.maxsize
        self.min_prices = [sys.maxsize for _ in range(n)]
        self.dst = dst
        self.k = k
        self.route = [[] for _ in range(n)]  # route[from][[to,price], ]
        for edge in flights:
            self.route[edge[0]].append((edge[1:]))

        # for id,route in enumerate(self.route):
        #     print(id,route)

        self.dfs(src, 0, 0)
        return self.min_price if self.GET_RES else -1


def test(data_test):
    s = Solution()
    return s.findCheapestPrice(*data_test)


if __name__ == '__main__':
    datas = [
        [3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1],  # 200
        [3,[[0,1,100],[1,2,100],[0,2,500]],0,2,0],  # 500
        [5,[[4,1,1],[1,2,3],[0,3,2],[0,4,10],[3,1,1],[1,4,3]],2,1,1],   # -1
        [17,[[0,12,28],[5,6,39],[8,6,59],[13,15,7],[13,12,38],[10,12,35],[15,3,23],[7,11,26],[9,4,65],[10,2,38],[4,7,7],[14,15,31],[2,12,44],[8,10,34],[13,6,29],[5,14,89],[11,16,13],[7,3,46],[10,15,19],[12,4,58],[13,16,11],[16,4,76],[2,0,12],[15,0,22],[16,12,13],[7,1,29],[7,14,100],[16,1,14],[9,6,74],[11,1,73],[2,11,60],[10,11,85],[2,5,49],[3,4,17],[4,9,77],[16,3,47],[15,6,78],[14,1,90],[10,5,95],[1,11,30],[11,0,37],[10,4,86],[0,8,57],[6,14,68],[16,8,3],[13,0,65],[2,13,6],[5,13,5],[8,11,31],[6,10,20],[6,2,33],[9,1,3],[14,9,58],[12,3,19],[11,2,74],[12,14,48],[16,11,100],[3,12,38],[12,13,77],[10,9,99],[15,13,98],[15,12,71],[1,4,28],[7,0,83],[3,5,100],[8,9,14],[15,11,57],[3,6,65],[1,3,45],[14,7,74],[2,10,39],[4,8,73],[13,5,77],[10,0,43],[12,9,92],[8,2,26],[1,7,7],[9,12,10],[13,11,64],[8,13,80],[6,12,74],[9,7,35],[0,15,48],[3,7,87],[16,9,42],[5,16,64],[4,5,65],[15,14,70],[12,0,13],[16,14,52],[3,10,80],[14,11,85],[15,2,77],[4,11,19],[2,7,49],[10,7,78],[14,6,84],[13,7,50],[11,6,75],[5,10,46],[13,8,43],[9,10,49],[7,12,64],[0,10,76],[5,9,77],[8,3,28],[11,9,28],[12,16,87],[12,6,24],[9,15,94],[5,7,77],[4,10,18],[7,2,11],[9,5,41]],13,4,13],#47
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{time.time() - t0}s')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

备注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！