Chuyến bay rẻ nhất trong K điểm dừng trong C++

Giới thiệu

Cho n thành phố và m chuyến bay có hướng (u, v, w) – từ u đến v giá w. Tìm giá rẻ nhất từ src đến dst với tối đa K điểm dừng (tức tối đa K+1 cạnh). Không có đường thì trả -1.

Thuật toán: Dijkstra biến thể (ưu tiên theo chi phí, theo dõi số stops)

Sử dụng priority queue (min-heap) lưu (cost, node, stops). Mảng cost[node][stops] lưu chi phí nhỏ nhất đến node với đúng stops bước. Khi pop ra node đích → trả về cost (vì heap ưu tiên cost nhỏ).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

struct State {
    int node, stops, cost;
    State(int n, int s, int c) : node(n), stops(s), cost(c) {}
    bool operator>(const State& other) const { return cost > other.cost; }
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<pair<int,int>>> graph(n);
        for (auto& f : flights) graph[f[0]].push_back({f[1], f[2]});

        vector<vector<int>> best(n, vector<int>(K+2, INT_MAX));
        priority_queue<State, vector<State>, greater<State>> pq;
        pq.push(State(src, 0, 0));
        best[src][0] = 0;

        while (!pq.empty()) {
            State cur = pq.top(); pq.pop();
            if (cur.node == dst) return cur.cost;
            if (cur.stops > K) continue;
            for (auto& [nei, w] : graph[cur.node]) {
                int nc = cur.cost + w;
                int ns = cur.stops + 1;
                if (nc < best[nei][ns]) {
                    best[nei][ns] = nc;
                    pq.push(State(nei, ns, nc));
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << ob.findCheapestPrice(3, flights, 0, 2, 1); // Output: 200
    return 0;
}

Phân tích

• Thời gian: O((V+E) log V) ~ O(E log V) với E = số chuyến bay.
• Không gian: O(V*K) cho mảng best.

Lưu ý: K có thể lên đến n-1. Giải pháp này hiệu quả hơn Bellman-Ford O(K*E) khi đồ thị thưa.