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``。 自建示例 -------- 更便宜的路线恰好使用允许的两个中转站: .. code-block:: text 输入: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,低于其他满足限制的路线。 没有中转额度时只能选择直飞: .. code-block:: text 输入:n = 3, flights = [[0,1,20],[1,2,20]], src = 0, dst = 2, k = 0 输出:-1 解释:唯一连接起终点的路线需要在城市 1 中转一次,而 k = 0 不允许中转。