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

LeetCode

发布日期: 2022-03-30

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

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

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

示例 1：

输入:

4
[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
0
3
2
输出: 700

method: Bellman Ford

从起点到终点最多经过k个点（k+1条边）的问题

处理负边权

判负环

dp[t][i]：从起点刚好经过t个航站到节点i所需的代价

外层循环枚举[1, k+1]，表示分别经过1,2,...,k+1个航站
内层需要枚举i前面的一个节点

这样结果就是dp[1][i],dp[2][i],...,dp[k+1][i]中的最小值

枚举i前面的每个节点，再看有没有到i的边了，这样比较麻烦
可以直接枚举每一条边，看看能不能更新dp[t][i]

const int inf = 0x3f3f3f3f;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<vector<int>> dp(k + 2, vector<int>(n, inf));
    dp[0][src] = 0;
    int res = inf;
    for (int i = 1; i <= k + 1; i ++) {
        for (auto f : flights) {    // 遍历每一条边
            int u = f[0], v = f[1], w = f[2];
            dp[i][v] = min(dp[i][v], dp[i - 1][u] + w);
        }
        res = min(res, dp[i][dst]);
    }
    return res == inf ? -1 : res;
}

二维数组就需要记录经过t个点的最小代价

$res = {\rm min} ~dp[t][dst], t = 1, 2, \ldots,k+1$

 0   1   2   3
 0  inf inf inf // 最多经过0条边 
inf 100 inf inf // 最多经过1条边 
inf inf 200 700 // 最多经过2条边 
300 inf inf 400 // 最多经过3条边 
inf 400 inf inf // 最多经过4条边 
            min=400

因为只涉及到两行，可以用滚动数组

const int inf = 0x3f3f3f3f;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<int> dp0(n, inf);
    vector<int> dp1(n, inf);
    dp0[src] = 0;
    for (int i = 1; i <= k + 1; i++) {
        dp1 = dp0;  // 先拷贝旧的行，更新
        for (auto f : flights) {
            int u = f[0], v = f[1], w = f[2];
            dp1[v] = min(dp1[v], dp0[u] + w);
        }
        dp0 = dp1;  // 新的行成为旧的行
    }
    return dp0[dst] == inf ? -1 : dp0[dst];
}

0  1   2   3
0 inf inf inf // 最多经过0条边 
0 100 inf inf // 最多经过1条边 
0 100 200 700 // 最多经过2条边 
0 100 200 400 // 最多经过3条边 
0 100 200 400 // 最多经过4条边

LeetCode 1928. 规定时间内到达终点的最小花费

一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证所有城市都由双向道路连接在一起。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。

每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。

一开始，你在城市 0 ，你想要在 maxTime 分钟以内（包含 maxTime 分钟）到达城市 n - 1 。旅行的费用为你经过的所有城市通行费之和（包括起点和终点城市的通行费）。

给你 maxTime，edges 和 passingFees ，请你返回完成旅行的最小费用，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。

示例 1：

输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。

method

dp[t][i]：从起点刚好经过时间t到节点i的最小代价
对于时间t=[1, maxTime]，枚举每一条边，如果可以从节点j到i使得代价更小，就更新dp[t][i]

dp[t][i] = min(dp[t][i], dp[t - cost(j,i)][j] + fee[i])

因为是双向边，所以也可以更新节点dp[t][j]
最后的结果是每个时间t所对应的dp[t][n-1]中的最小值

$res = {\rm min} ~dp[t][n-1], t = 1, 2, \ldots, \rm maxTime$

const int inf = 0x3f3f3f3f;
int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
    int n = passingFees.size();
    int dp[maxTime + 1][n];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = passingFees[0];
    int res = inf;
    for (int t = 1; t <= maxTime; t++) {
        for (auto& e : edges) { // 不加引用会超时
            int i = e[0], j = e[1], w = e[2];
            if (t >= w) {
                dp[t][j] = min(dp[t][j], dp[t - w][i] + passingFees[j]);
                dp[t][i] = min(dp[t][i], dp[t - w][j] + passingFees[i]);
            }
        }
        res = min(res, dp[t][n - 1]);
    }
    return res == inf ? -1 : res;
}