Khóa học CTDL và GT

Bài 22.4. Shortest Path Faster Algorithm (SPFA)

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Ở các bài trước, chúng ta đã khám phá thuật toán Dijkstra - một công cụ mạnh mẽ để tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. Tuy nhiên, thế giới của đồ thị không chỉ giới hạn ở những cạnh có trọng số dương. Đôi khi, các cạnh có thể mang trọng số âm, thể hiện chi phí giảm đi, hoặc lợi ích đạt được, hoặc đơn vị đo lường nào đó có thể âm. Khi đó, Dijkstra "bó tay" vì nguyên lý hoạt động của nó dựa trên giả định rằng việc thêm một cạnh mới sẽ không làm giảm tổng trọng số đường đi đã được "chốt".

Vậy làm thế nào để tìm đường đi ngắn nhất trong đồ thị có cạnh âm? Một thuật toán cổ điển và đáng tin cậy là Bellman-Ford. Thuật toán này hoạt động bằng cách lặp đi lặp lại việc relax (thư giãn) tất cả các cạnh của đồ thị V-1 lần, trong đó V là số đỉnh. Mặc dù Bellman-Ford đảm bảo tìm ra đường đi ngắn nhất (nếu không có chu trình âm) và phát hiện được chu trình âm, độ phức tạp thời gian của nó là O(V*E), có thể khá chậm trên các đồ thị lớn và dày.

Trong bài viết này, chúng ta sẽ tìm hiểu về Shortest Path Faster Algorithm (SPFA). Đúng như tên gọi của nó, SPFA là một thuật toán tìm đường đi ngắn nhất được thiết kế để chạy nhanh hơn trong thực tế so với Bellman-Ford trên nhiều loại đồ thị, mặc dù về lý thuyết, độ phức tạp trong trường hợp xấu nhất vẫn là O(V*E). SPFA cũng có khả năng xử lý đồ thị có cạnh âm và phát hiện chu trình âm.

Tại sao SPFA lại "Faster"?

Ý tưởng chính của SPFA là một sự tối ưu hóa dựa trên quan sát của thuật toán Bellman-Ford. Trong Bellman-Ford, mỗi lần lặp, chúng ta cố gắng relax tất cả các cạnh. Việc relax một cạnh (u, v) với trọng số w có nghĩa là kiểm tra xem liệu đường đi đến v thông qua u có ngắn hơn đường đi hiện tại đến v hay không: if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; }.

SPFA nhận thấy rằng, nếu một đỉnh u có khoảng cách dist[u] không được cập nhật (không được giảm đi) trong một lần lặp, thì việc relax các cạnh đi ra từ u ((u, v)) trong lần lặp tiếp theo không thể làm giảm khoảng cách dist[v] thông qua u hơn nữa (vì dist[u] không thay đổi). Chỉ những đỉnh u mà khoảng cách dist[u] đã được giảm mới có khả năng cải thiện khoảng cách đến các đỉnh lân cận v.

Do đó, thay vì lặp qua tất cả các đỉnh và tất cả các cạnh một cách mù quáng, SPFA chỉ tập trung vào việc relax các cạnh đi ra từ những đỉnh mà khoảng cách của chúng vừa được cập nhật. Để quản lý các đỉnh cần xử lý này, SPFA sử dụng một hàng đợi (queue).

Cơ chế hoạt động của SPFA

1. Khởi tạo:

   • Giống như các thuật toán đường đi ngắn nhất khác, chúng ta khởi tạo mảng dist lưu trữ khoảng cách ngắn nhất từ đỉnh nguồn s đến tất cả các đỉnh khác. dist[s] được đặt bằng 0, và dist[v] với mọi đỉnh v != s được đặt bằng vô cùng (infinity).
   • Sử dụng một hàng đợi Q. Đưa đỉnh nguồn s vào hàng đợi.
   • Sử dụng một mảng boolean in_queue để theo dõi xem một đỉnh hiện có đang nằm trong hàng đợi hay không. Ban đầu, in_queue[s] là true, tất cả đỉnh khác là false.
   • (Để phát hiện chu trình âm) Sử dụng một mảng count để đếm số lần mỗi đỉnh được đưa vào hàng đợi. Khởi tạo count[s] = 1, các đỉnh khác bằng 0.

2. Quá trình lặp:

   • Trong khi hàng đợi Q chưa rỗng:
     • Lấy đỉnh u ra khỏi đầu hàng đợi. Đặt in_queue[u] = false.
     • Đối với mỗi đỉnh kề v của u và cạnh (u, v) có trọng số w:
       • Kiểm tra điều kiện relax: if (dist[u] + w < dist[v]).
       • Nếu điều kiện đúng (tìm thấy đường đi ngắn hơn đến v qua u):
         • Cập nhật khoảng cách: dist[v] = dist[u] + w.
         • Nếu v hiện không có trong hàng đợi (in_queue[v] là false):
           • Đưa v vào cuối hàng đợi: Q.push(v).
           • Đặt in_queue[v] = true.
           • Tăng bộ đếm count[v] lên 1.
           • Kiểm tra chu trình âm: Nếu count[v] trở nên lớn hơn số đỉnh của đồ thị (V), điều đó chứng tỏ có một chu trình âm có thể truy cập được từ đỉnh nguồn. Ta có thể dừng thuật toán và báo cáo.

3. Kết quả:

   • Nếu thuật toán kết thúc mà không phát hiện chu trình âm, mảng dist sẽ chứa khoảng cách ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác. Nếu dist[v] vẫn bằng vô cùng, nghĩa là đỉnh v không thể truy cập được từ đỉnh nguồn.
   • Nếu phát hiện chu trình âm, không có đường đi ngắn nhất xác định trong đồ thị đó.

Độ phức tạp và so sánh

• Độ phức tạp thời gian: Trong trường hợp xấu nhất, SPFA vẫn có thể hoạt động giống như Bellman-Ford và đạt độ phức tạp O(V*E). Tuy nhiên, trên nhiều loại đồ thị thực tế (ví dụ: đồ thị thưa, hoặc đồ thị có cấu trúc nhất định), SPFA có thể chạy nhanh hơn đáng kể, gần với O(E) hoặc O(kE) với k là một hằng số nhỏ.
• Độ phức tạp không gian: O(V+E) để lưu trữ đồ thị (danh sách kề), O(V) cho mảng dist, in_queue, count, và hàng đợi Q. Tổng cộng là O(V+E).

So sánh với các thuật toán khác:

• Dijkstra:
  • Chỉ dùng cho trọng số không âm.
  • Nhanh hơn SPFA trên đồ thị có trọng số không âm (thường là O(E log V) hoặc O(E + V log V) với hàng đợi ưu tiên).
  • Không phát hiện chu trình âm.
• Bellman-Ford:
  • Xử lý được trọng số âm và phát hiện chu trình âm.
  • Độ phức tạp O(V*E) được đảm bảo, không phụ thuộc vào cấu trúc đồ thị cụ thể.
  • Độ phức tạp không gian O(V+E).
• SPFA:
  • Xử lý được trọng số âm và phát hiện chu trình âm.
  • Độ phức tạp lý thuyết O(V*E), nhưng thường nhanh hơn trong thực tế.
  • Độ phức tạp không gian O(V+E).

Lưu ý quan trọng: Mặc dù tên là "Faster", SPFA không phải lúc nào cũng nhanh hơn Bellman-Ford trong mọi trường hợp. Tồn tại những cấu trúc đồ thị có thể khiến SPFA đạt đến hiệu suất O(V*E), thậm chí còn chậm hơn Bellman-Ford một chút do chi phí quản lý hàng đợi. Do đó, trong các môi trường cạnh tranh lập trình hoặc khi cần đảm bảo hiệu suất thời gian chặt chẽ cho trường hợp xấu nhất, Bellman-Ford thường là lựa chọn an toàn hơn nếu O(VE) chấp nhận được. SPFA thường được ưu tiên khi trọng số âm tồn tại và kinh nghiệm cho thấy nó chạy nhanh trên dạng đồ thị cụ thể đang xét, hoặc đơn giản là khi Bellman-Ford quá chậm và SPFA mang lại hiệu suất thực tế tốt hơn.

Ví dụ minh họa 1: Đồ thị có cạnh âm không có chu trình âm

Chúng ta xét đồ thị có 5 đỉnh (0 đến 4) và các cạnh có trọng số như sau:

• 0 -> 1 (trọng số 1)
• 0 -> 2 (trọng số 5)
• 1 -> 2 (trọng số 2)
• 1 -> 3 (trọng số 4)
• 2 -> 3 (trọng số -2)
• 3 -> 4 (trọng số 3)

Chúng ta sẽ tìm đường đi ngắn nhất từ đỉnh nguồn 0.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const long long INF = std::numeric_limits<long long>::max(); // Sử dụng giá trị vô cùng lớn

struct Edge {
    int to;
    int weight;
};

int main() {
    int V = 5; // Số đỉnh
    std::vector<std::vector<Edge>> adj(V); // Danh sách kề

    // Thêm các cạnh vào đồ thị
    adj[0].push_back({1, 1});
    adj[0].push_back({2, 5});
    adj[1].push_back({2, 2});
    adj[1].push_back({3, 4});
    adj[2].push_back({3, -2}); // Cạnh âm
    adj[3].push_back({4, 3});

    int start_node = 0; // Đỉnh nguồn

    std::vector<long long> dist(V, INF); // Mảng khoảng cách, khởi tạo bằng vô cùng
    std::vector<bool> in_queue(V, false); // Theo dõi đỉnh có trong hàng đợi
    std::queue<int> q; // Hàng đợi SPFA

    // Khởi tạo cho đỉnh nguồn
    dist[start_node] = 0;
    q.push(start_node);
    in_queue[start_node] = true;

    // SPFA algorithm
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false; // Đỉnh u không còn trong hàng đợi

        // Duyệt qua các đỉnh kề của u
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // Kiểm tra điều kiện relax: dist[u] + weight < dist[v]
            // Cần kiểm tra dist[u] != INF để tránh tràn số khi cộng với weight
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight; // Cập nhật khoảng cách

                // Nếu đỉnh v chưa có trong hàng đợi, thêm vào
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    // Trong ví dụ này không có chu trình âm, nên bỏ qua đếm cho đơn giản
                    // (Sẽ thêm vào ví dụ sau để phát hiện chu trình âm)
                }
            }
        }
    }

    // In kết quả
    std::cout << "Shortest distances from node " << start_node << ":" << std::endl;
    for (int i = 0; i < V; ++i) {
        if (dist[i] == INF) {
            std::cout << "To node " << i << ": Not reachable" << std::endl;
        } else {
            std::cout << "To node " << i << ": " << dist[i] << std::endl;
        }
    }

    return 0;
}

Giải thích code:

1. Include Headers: Bao gồm iostream cho input/output, vector cho danh sách kề, queue cho hàng đợi, và limits để lấy giá trị vô cùng lớn.
2. INF: Định nghĩa một giá trị rất lớn để biểu diễn khoảng cách ban đầu là vô cùng. Sử dụng long long để tránh tràn số khi tính tổng khoảng cách.
3. Edge Struct: Cấu trúc đơn giản để lưu thông tin về cạnh (đỉnh đến và trọng số).
4. adj: std::vector<std::vector<Edge>> là cách biểu diễn đồ thị bằng danh sách kề. adj[u] là một vector chứa tất cả các cạnh đi ra từ đỉnh u.
5. Khởi tạo:
   • dist: Vector long long kích thước V, tất cả được gán giá trị INF.
   • in_queue: Vector bool kích thước V, tất cả được gán giá trị false. Dùng để kiểm tra nhanh một đỉnh có đang trong hàng đợi hay không.
   • q: Hàng đợi kiểu int để lưu trữ các đỉnh cần xử lý.
   • dist[start_node] được đặt là 0, và đỉnh nguồn được đưa vào hàng đợi, đánh dấu in_queue[start_node] = true.
6. Vòng lặp SPFA:
   • Vòng while (!q.empty()) chạy cho đến khi không còn đỉnh nào cần xử lý trong hàng đợi.
   • Lấy đỉnh u ra khỏi hàng đợi và đặt in_queue[u] = false.
   • Duyệt qua tất cả các cạnh (u, v) đi ra từ u.
   • Điều kiện dist[u] != INF: Quan trọng để tránh trường hợp INF + weight gây tràn số hoặc kết quả không mong muốn khi dist[u] chưa bao giờ được cập nhật từ một đỉnh reachable.
   • Điều kiện dist[u] + weight < dist[v]: Đây là bước relax. Nếu đường đi qua u ngắn hơn đường đi hiện tại đến v, ta cập nhật dist[v].
   • Kiểm tra !in_queue[v]: Nếu dist[v] được cập nhật VÀ đỉnh v hiện không có trong hàng đợi, ta đưa v vào hàng đợi và đánh dấu in_queue[v] = true. Việc chỉ thêm v vào hàng đợi khi nó không có trong hàng đợi là một biến thể phổ biến của SPFA giúp tránh dư thừa công việc, mặc dù một số biến thể khác cho phép thêm lại đỉnh vào hàng đợi nếu khoảng cách của nó được cải thiện.
7. In kết quả: Sau khi vòng lặp kết thúc, mảng dist chứa khoảng cách ngắn nhất.

Kết quả chạy chương trình này sẽ là:

Shortest distances from node 0:
To node 0: 0
To node 1: 1
To node 2: 3
To node 3: 1
To node 4: 4

Hãy thử kiểm tra:

• 0 -> 0: 0 (đúng)
• 0 -> 1: 0 -> 1 (trọng số 1) -> 1 (đúng)
• 0 -> 2: 0 -> 1 -> 2 (trọng số 1+2 = 3) -> 3 (ngắn hơn đường trực tiếp 0->2 với trọng số 5, đúng)
• 0 -> 3: 0 -> 1 -> 2 -> 3 (trọng số 1+2-2 = 1) -> 1 (ngắn hơn đường 0->1->3 với trọng số 1+4 = 5, đúng)
• 0 -> 4: 0 -> 1 -> 2 -> 3 -> 4 (trọng số 1+2-2+3 = 4) -> 4 (đúng)

Ví dụ minh họa 2: Đồ thị có chu trình âm

Bây giờ, chúng ta xét một đồ thị có chu trình âm có thể truy cập được từ đỉnh nguồn. Chu trình âm là một chu trình mà tổng trọng số các cạnh trên đó là âm. Sự tồn tại của chu trình âm khiến cho bài toán đường đi ngắn nhất trở nên không xác định, vì ta có thể đi quanh chu trình âm vô số lần để làm giảm tổng trọng số đường đi đến vô cùng âm. SPFA có thể phát hiện điều này.

Xét đồ thị có 4 đỉnh (0 đến 3) và các cạnh:

• 0 -> 1 (trọng số 1)
• 1 -> 2 (trọng số 1)
• 2 -> 1 (trọng số -2)
• 2 -> 3 (trọng số 1)

Chu trình 1 -> 2 -> 1 có tổng trọng số 1 + (-2) = -1, là một chu trình âm. Đỉnh 0 có thể đến đỉnh 1, và đỉnh 1 nằm trên chu trình âm. Do đó, chu trình âm này có thể truy cập được từ đỉnh nguồn 0.

Để phát hiện chu trình âm, chúng ta thêm mảng count vào thuật toán. Nếu một đỉnh v được đưa vào hàng đợi (tức là khoảng cách đến v được cải thiện) số lần lớn hơn V (tổng số đỉnh), thì chắc chắn có một chu trình âm.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const long long INF = std::numeric_limits<long long>::max();

struct Edge {
    int to;
    int weight;
};

int main() {
    int V = 4; // Số đỉnh
    std::vector<std::vector<Edge>> adj(V); // Danh sách kề

    // Thêm các cạnh
    adj[0].push_back({1, 1});
    adj[1].push_back({2, 1});
    adj[2].push_back({1, -2}); // Tạo chu trình âm 1 -> 2 -> 1 (-1)
    adj[2].push_back({3, 1});

    int start_node = 0; // Đỉnh nguồn

    std::vector<long long> dist(V, INF);
    std::vector<bool> in_queue(V, false);
    std::vector<int> count(V, 0); // Mảng đếm số lần đỉnh được đưa vào hàng đợi
    std::queue<int> q;

    // Khởi tạo
    dist[start_node] = 0;
    q.push(start_node);
    in_queue[start_node] = true;
    count[start_node] = 1; // Đỉnh nguồn được đưa vào hàng đợi 1 lần ban đầu

    bool negative_cycle_detected = false;

    // SPFA algorithm với phát hiện chu trình âm
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        // Duyệt qua các đỉnh kề
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;

                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;

                    // Tăng bộ đếm và kiểm tra chu trình âm
                    count[v]++;
                    if (count[v] >= V) { // Nếu đỉnh v được đưa vào hàng đợi >= V lần
                        negative_cycle_detected = true;
                        break; // Thoát khỏi vòng lặp for
                    }
                }
            }
        }

        if (negative_cycle_detected) {
            break; // Thoát khỏi vòng lặp while
        }
    }

    // In kết quả
    if (negative_cycle_detected) {
        std::cout << "Negative cycle detected reachable from node " << start_node << "!" << std::endl;
    } else {
        std::cout << "Shortest distances from node " << start_node << ":" << std::endl;
        for (int i = 0; i < V; ++i) {
            if (dist[i] == INF) {
                std::cout << "To node " << i << ": Not reachable" << std::endl;
            } else {
                std::cout << "To node " << i << ": " << dist[i] << std::endl;
            }
        }
    }

    return 0;
}

Giải thích code (phần khác biệt so với ví dụ 1):

1. count array: Thêm std::vector<int> count(V, 0); để đếm số lần mỗi đỉnh được đưa vào hàng đợi.
2. Increment count[v]: Khi một đỉnh v được đưa vào hàng đợi (vì khoảng cách đến nó được cải thiện), chúng ta tăng count[v].
3. Negative Cycle Check: Ngay sau khi tăng count[v], chúng ta kiểm tra if (count[v] >= V). Nếu điều này đúng, chúng ta đặt cờ negative_cycle_detected = true và thoát khỏi các vòng lặp hiện tại. Tại sao lại là V lần? Vì trong một đồ thị không có chu trình âm, đường đi ngắn nhất từ đỉnh nguồn đến bất kỳ đỉnh nào có tối đa V-1 cạnh. Điều này có nghĩa là một đỉnh có thể được relax và đưa vào hàng đợi tối đa V-1 lần trên các đường đi khác nhau có độ dài tăng dần (hoặc giữ nguyên). Nếu nó được đưa vào hàng đợi lần thứ V (hoặc hơn), tức là khoảng cách đến nó vẫn tiếp tục được cải thiện sau khi đã xét qua mọi đường đi "thẳng" có thể, điều này chỉ xảy ra khi có một chu trình âm làm giảm liên tục tổng trọng số đường đi.
4. Thoát vòng lặp: Sử dụng các lệnh break để thoát ngay khi phát hiện chu trình âm.
5. Kết quả: Sau vòng lặp chính, kiểm tra cờ negative_cycle_detected để in ra thông báo phù hợp.

Kết quả chạy chương trình này sẽ là:

Negative cycle detected reachable from node 0!

Đúng như dự đoán, thuật toán đã phát hiện ra chu trình âm có thể truy cập được từ đỉnh nguồn.

Bài tập ví dụ:

Giảm giá chuyến bay

Trong một buổi phỏng vấn, FullHouse Dev được đưa ra một bài toán thú vị về việc tối ưu chi phí chuyến bay. Họ được yêu cầu tìm ra tuyến bay có giá rẻ nhất từ Syrjälä đến Metsälä, với một phiếu giảm giá đặc biệt.

Bài toán

Nhiệm vụ của bạn là tìm tuyến bay có giá thấp nhất từ Syrjälä đến Metsälä. Bạn có một phiếu giảm giá, cho phép giảm một nửa giá vé của bất kỳ chuyến bay nào trong tuyến đường. Tuy nhiên, bạn chỉ được sử dụng phiếu giảm giá một lần duy nhất. Khi sử dụng phiếu giảm giá cho một chuyến bay có giá \(x\), giá của nó sẽ trở thành \(\lfloor x/2 \rfloor\) (được làm tròn xuống thành số nguyên).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số lượng đường bay. Các thành phố được đánh số từ \(1,2,\ldots,n\). Thành phố 1 là Syrjälä, và thành phố \(n\) là Metsälä.
• \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): chuyến bay bắt đầu từ thành phố \(a\), kết thúc tại thành phố \(b\), và có giá \(c\). Mỗi chuyến bay chỉ một chiều. Bạn có thể giả định rằng luôn có thể đi từ Syrjälä đến Metsälä.

OUTPUT FORMAT:

• In ra một số nguyên: giá của tuyến đường rẻ nhất từ Syrjälä đến Metsälä.

Ràng buộc:

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Ví dụ

INPUT

3 4
1 2 3
2 3 1
1 3 7
2 1 5

OUTPUT

2

Giải thích

Tuyến đường tối ưu là đi từ thành phố 1 đến thành phố 2 (giá 3), sau đó từ thành phố 2 đến thành phố 3 (giá 1). Sử dụng phiếu giảm giá cho chuyến bay đầu tiên sẽ giảm giá từ 3 xuống 1. Vì vậy, tổng chi phí là 1 + 1 = 2. Tuyệt vời, đây là hướng dẫn giải bài toán "Giảm giá chuyến bay" bằng C++ theo hướng thuật toán và cấu trúc dữ liệu, không cung cấp code hoàn chỉnh:

1. Nhận diện bài toán: Đây là bài toán tìm đường đi ngắn nhất trên đồ thị có hướng, có trọng số dương (giá vé). Điểm đặc biệt là có một "phiếu giảm giá" có thể áp dụng một lần duy nhất cho một cạnh bất kỳ để giảm trọng số của cạnh đó.

2. Mở rộng trạng thái (State): Bài toán tiêu chuẩn chỉ cần trạng thái là nút hiện tại (current_node). Tuy nhiên, việc sử dụng phiếu giảm giá làm thay đổi trọng số của một cạnh và điều này ảnh hưởng đến các đường đi tiếp theo. Ta cần biết liệu phiếu giảm giá đã được sử dụng hay chưa khi đến một nút. Do đó, ta mở rộng trạng thái thành (current_node, discount_used).

   • discount_used = 0: Phiếu giảm giá chưa được sử dụng trên đường đi từ thành phố 1 đến current_node.
   • discount_used = 1: Phiếu giảm giá đã được sử dụng trên một cạnh nào đó trên đường đi từ thành phố 1 đến current_node.

3. Sử dụng thuật toán Dijkstra: Vì trọng số các cạnh (giá vé) là không âm, thuật toán Dijkstra là phù hợp để tìm đường đi ngắn nhất. Tuy nhiên, ta sẽ áp dụng Dijkstra trên "đồ thị trạng thái" đã mở rộng.

   • Mảng khoảng cách: Thay vì mảng 1D dist[N], ta dùng mảng 2D dist[N][2].
     • dist[u][0] lưu trữ chi phí nhỏ nhất để đi từ thành phố 1 đến thành phố u mà chưa sử dụng phiếu giảm giá.
     • dist[u][1] lưu trữ chi phí nhỏ nhất để đi từ thành phố 1 đến thành phố u sau khi đã sử dụng phiếu giảm giá trên một cạnh bất kỳ trước đó.
   • Hàng đợi ưu tiên (Priority Queue): Hàng đợi sẽ lưu trữ các phần tử có dạng (cost, node, discount_used). Phần tử có cost nhỏ nhất sẽ được ưu tiên lấy ra.
   • Khởi tạo: Khởi tạo tất cả giá trị trong mảng dist bằng vô cùng. dist[1][0] = 0 (chi phí đến thành phố 1 là 0, chưa dùng giảm giá). Đẩy (0, 1, 0) vào hàng đợi ưu tiên.

4. Quá trình thư giãn cạnh (Relaxation): Khi lấy ra trạng thái (d, u, used_discount) từ hàng đợi ưu tiên (với d là chi phí, u là thành phố, used_discount là trạng thái giảm giá):

   • Nếu d > dist[u][used_discount], bỏ qua vì đã tìm thấy đường đi tốt hơn đến trạng thái này rồi.
   • Xét tất cả các cạnh đi ra từ u đến v với giá w.
     • Trường hợp 1: KHÔNG sử dụng giảm giá cho cạnh (u, v):
       • Chi phí mới đến v là d + w.
       • Trạng thái giảm giá vẫn là used_discount.
       • Nếu d + w < dist[v][used_discount]: Cập nhật dist[v][used_discount] = d + w và đẩy (dist[v][used_discount], v, used_discount) vào hàng đợi ưu tiên.
     • Trường hợp 2: Sử dụng giảm giá cho cạnh (u, v):
       • Chỉ thực hiện được nếu used_discount == 0 (phiếu chưa được dùng).
       • Giá mới của cạnh là floor(w / 2).
       • Chi phí mới đến v là d + floor(w / 2).
       • Trạng thái giảm giá trở thành 1.
       • Nếu d + floor(w / 2) < dist[v][1]: Cập nhật dist[v][1] = d + floor(w / 2) và đẩy (dist[v][1], v, 1) vào hàng đợi ưu tiên.

5. Kết quả cuối cùng: Sau khi thuật toán Dijkstra kết thúc (hàng đợi rỗng), chi phí nhỏ nhất để đến thành phố n có thể là đường đi không dùng giảm giá (dist[n][0]) hoặc đường đi có dùng giảm giá một lần (dist[n][1]). Tuy nhiên, vì bài toán yêu cầu tìm tuyến bay rẻ nhất có sử dụng phiếu giảm giá một lần tối ưu, đáp án chính là dist[n][1]. (Mặc dù đôi khi dist[n][0] có thể nhỏ hơn nếu việc giảm giá không giúp ích, nhưng dist[n][1] sẽ nắm bắt chi phí nhỏ nhất khi ít nhất một lần việc giảm giá đã được xem xét và áp dụng tối ưu).

6. Kiểu dữ liệu: Do giá vé có thể lên tới $10^9$ và số lượng thành phố/đường bay khá lớn, tổng chi phí có thể vượt quá giới hạn của kiểu int. Hãy sử dụng long long cho các giá trị khoảng cách/chi phí trong mảng dist và trong hàng đợi ưu tiên.

7. Cấu trúc dữ liệu: Sử dụng danh sách kề (adjacency list) để lưu trữ đồ thị: vector<pair<int, int>> adj[N] trong đó adj[u] chứa danh sách các cặp {v, w} biểu thị cạnh từ u đến v với trọng số w.

Làm thêm nhiều bài tập miễn phí tại đây