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

题目描述

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

解法：DP（C++）

$dp(k,v)$表示最多中转$k$站由$src$到$v$的最低花费，则转移方程为$dp(k,v)=min(dp(k-1,v),dp(k-1,u)+w(u,v))$

$backup[...]$数组主要是用于求$dp(k-1,u)+w(u,v)$，避免在一个$dp[...]$数组里面操作更改了某一状态

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = 1e9;
        vector<long> dist(n, INF);
        vector<long> backup(n);

        dist[src] = 0;
        for(int i=0;i<=K;i++)
        {
            backup.assign(dist.begin(), dist.end());
            for(auto& flight: flights)
                dist[flight[1]] = min(dist[flight[1]], backup[flight[0]]+flight[2]);
        }
        return dist[dst] == INF?-1:dist[dst];
    }
};