0787. Cheapest Flights Within K Stops

题目信息

题号:

0787

难度:

Medium

主题:

有向图、受限路径、最低费用

原题:

LeetCode 0787

重点:

每条航班有方向和价格;至多 k 个中转城市等价于至多乘坐 k + 1 段航班,需要返回满足限制的最低总价或 -1

题目重述

有 n 个城市,编号为 0 至 n - 1。数组 flights 中每个三元组 [from, to, price] 表示一班从 from 飞往 to 的单向航班,票价为 price。任意两个城市之间至多存在一班同方向航班。

给定起点 src、终点 dst 和整数 k,请在中途经过的城市数量不超过 k 的条件下,返回从 src 到 dst 的最低总票价。起点和终点不计为中转城市,因此合法路线最多包含 k + 1 段航班。若不存在符合中转限制的路线,返回 -1。

2 <= n <= 100,航班数在 [0, n * (n - 1) / 2] 范围内;城市编号合法,航班起终点不同,票价在 [1, 10^4] 范围内;0 <= src, dst, k < n 且 src != dst。

自建示例

更便宜的路线恰好使用允许的两个中转站:

输入:n = 5, flights = [[0,1,60],[1,4,60],[0,2,30],[2,3,30],[3,4,30],[0,4,200]], src = 0, dst = 4, k = 2
输出:90
解释:路线 0 -> 2 -> 3 -> 4 经过城市 2、3 两个中转站,总价为 30 + 30 + 30 = 90,低于其他满足限制的路线。

没有中转额度时只能选择直飞:

输入:n = 3, flights = [[0,1,20],[1,2,20]], src = 0, dst = 2, k = 0
输出:-1
解释:唯一连接起终点的路线需要在城市 1 中转一次,而 k = 0 不允许中转。