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

题目描述

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

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

数据范围

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

样例

输入样例1：

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1

输出样例1：

样例1解释：

城市航班图如下：

995

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

输入样例2：

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0

输出样例2：

样例2解释：

城市航班图如下：

995

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

思路

bellman-ford的模板题。除了起点和终点，中间最多经过 $k$ 个点，所以一共有 $k + 2$ 个点，就有 $k + 1$ 条边。

代码

C++

#define N 105

class Solution {
    int dist[N], backup[N];
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        memset(dist, 0x3f, sizeof dist);
        dist[src] = 0;
        for ( int i = 0; i <= k; i ++ )
        {
            memcpy(backup, dist, sizeof dist);
            for ( auto &p : flights )
            {
                int a = p[0], b = p[1], w = p[2];
                dist[b] = min(dist[b], backup[a] + w);
            }
        }
        return dist[dst] == 0x3f3f3f3f ? -1 : dist[dst];
    }
};

Java

class Solution {
    final int N = 105, INF = 0x3f3f3f3f;
    int dist[] = new int[N], backup[] = new int[N];

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        for ( int i = 0; i < N; i ++ ) dist[i] = INF;
        dist[src] = 0;
        k ++;
        while ( k-- > 0 )
        {
            System.arraycopy(dist, 0, backup, 0, N);
            for ( int p[] : flights )
            {
                int a = p[0], b = p[1], w = p[2];
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}