Cheapest Flights Within K Stops – หาเที่ยวบินราคาถูกที่สุดใน C++

ปัญหา: Cheapest Flights Within K Stops

มี n เมือง, m เที่ยวบิน แต่ละเที่ยวบิน: u → v ราคา w
กำหนดเมืองต้นทาง src, ปลายทาง dst, และจำนวนจุดหยุดสูงสุด K
หา ราคาต่ำสุด จาก src ไป dst โดยหยุดไม่เกิน K ครั้ง (คือใช้ขอบได้มากที่สุด K+1 ขอบ)
ไม่มีเส้นทาง → คืน -1

ตัวอย่าง

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, K = 1

เส้นทาง: 0 → 1 → 2 (1 stop) ราคา 200 < 500 (ตรง) → Output: 200

แนวทางแก้ปัญหา: Modified Dijkstra / BFS with Priority Queue

ข้อสังเกต

Dijkstra ธรรมดาไม่ได้ เพราะต้องจำกัดจำนวน stops → State ต้องรวม (node, stops)

State: (cost, node, stops)

• Priority Queue เรียงตาม cost น้อยไปมาก (Min-heap)
• cost[u][stops] = ราคาต่ำสุดถึง u ด้วย stops ครั้ง
• Pop state → ถ้า node == dst → คืน cost (เจอคำตอบแรก = ถูกสุด)
• ถ้า stops > K+1 → ข้าม
• Relax เพื่อนบ้าน: ถ้า cost[v][stops+1] > cost[u][stops] + w → อัปเดต + push

ตัวอย่างโค้ด 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) {
        // Graph: adjacency list
        vector<vector<pair<int,int>>> graph(n);
        for (auto& f : flights)
            graph[f[0]].emplace_back(f[1], f[2]);

        // cost[node][stops] = min cost
        vector<vector<int>> cost(n, vector<int>(K+2, INT_MAX));
        priority_queue<State, vector<State>, greater<State>> pq;

        pq.emplace(src, 0, 0);
        cost[src][0] = 0;

        while (!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            int u = cur.node, stops = cur.stops, c = cur.cost;

            if (u == dst) return c; // เจอปลายทาง = ถูกสุด (PQ เรียง cost)
            if (stops > K) continue; // เกิน stops limit

            for (auto& [v, w] : graph[u]) {
                int nc = c + w;
                if (nc < cost[v][stops+1]) {
                    cost[v][stops+1] = nc;
                    pq.emplace(v, stops+1, 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); // 200
    return 0;
}

วิธีอื่น: Bellman-Ford (K+1 รอบ)

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;

    for (int i = 0; i <= K; i++) {
        vector<int> tmp = dist;
        for (auto& f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (dist[u] != INT_MAX)
                tmp[v] = min(tmp[v], dist[u] + w);
        }
        dist = tmp;
    }
    return dist[dst] == INT_MAX ? -1 : dist[dst];
}

ความซับซ้อน

ข้อสังเกต

• LeetCode 787 – ปัญหา Shortest Path with Constraint
• Dijkstra เร็วกว่าเวลา K ใหญ่, Bellman-Ford เข้าใจง่ายกว่า
• State (node, stops) สำคัญ – ไม่อาจใช้แค่ node ได้