题目描述

有 $n$ 个城市通过一些航班连接。给你一个长度为 $m$ 的数组 $flights$ ，其中 $flights[i] = [from_i, to_i, price_i]$ ，表示该航班都从城市 $from_i$ 开始，以价格 $price_i$ 抵达 $to_i$。

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

输入格式

第一行空格隔开的两个整数 $n$ 和 $m$；

接下来的 $m$ 行，每行空格隔开的三个整数分别表示 $from_i, to_i, price_i$；

最后一行三个整数表示$src$， $dst$ 和 $k$。

输出格式

一行一个整数，表示答案。

示例 1：

4 5
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200
0 3 1

700

解释: 城市航班图如上

从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。

请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。

示例 2：

3 3
0 1 100
1 2 100
0 2 500
0 2 1

200

解释:

城市航班图如上

从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。

示例 3：

3 3
0 1 100
1 2 100
0 2 500
0 2 0

500

解释：

城市航班图如上

从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 500。

提示：

• $1 <= n <= 100$
• $0 <= flights.length <= (n * (n - 1) / 2)$
• $flights[i].length == 3$
• $0 <= from_i, to_i < n$
• $from_i != to_i$
• $1 <= price_i <= 10^4$
• 航班没有重复，且不存在自环
• $0 <= src, dst, k < n$
• $src != dst$

Source

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