K 站中转内最便宜的航班

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        int dist[n];
        memset(dist, 0x3f, sizeof(dist));
        int backup[n];
        dist[src] = 0;

        for (int i = 0; i <= k; i++) {
            memcpy(backup, dist, sizeof(dist));
            for (int j = 0; j < flights.size(); j++) {
                int a = flights[j][0], b = flights[j][1], w = flights[j][2];
                dist[b] = min(dist[b], backup[a] + w); 
            }
        }

        if (dist[dst] > 0x3f3f3f3f / 2) return -1;
        return dist[dst];
    }
};