Khóa học CTDL và GT

Bài 23.2. Ứng dụng Tarjan trong tìm cầu

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! Hôm nay, chúng ta sẽ lặn sâu vào một trong những giải thuật trên đồ thị mạnh mẽ và thanh lịch nhất: Giải thuật Tarjan. Cụ thể, chúng ta sẽ khám phá ứng dụng của nó trong việc xác định cầu trong đồ thị.

Cầu Là Gì? Tại Sao Lại Quan Trọng?

Trong lý thuyết đồ thị, một cầu (bridge) là một cạnh mà khi ta loại bỏ nó, số lượng các thành phần liên thông (connected components) trong đồ thị sẽ tăng lên. Nói cách khác, cầu là những cạnh quan trọng bậc nhất trong việc giữ cho đồ thị được "kết nối" với nhau.

Hãy tưởng tượng đồ thị của chúng ta mô tả một mạng lưới đường bộ, nơi các đỉnh là thành phố và các cạnh là con đường nối chúng. Nếu một con đường là cầu, điều đó có nghĩa là nếu con đường đó bị đóng, việc di chuyển giữa hai nhóm thành phố sẽ trở nên bất khả thi. Điều này có ý nghĩa sống còn trong nhiều ứng dụng thực tế:

• Mạng máy tính: Tìm cầu giúp xác định các kết nối yếu nhất, nếu bị đứt sẽ chia mạng thành nhiều phần.
• Mạng giao thông: Tìm cầu giúp xác định các tuyến đường thiết yếu mà việc tắc nghẽn hoặc phá hủy sẽ gây ảnh hưởng lớn đến luồng di chuyển.
• Mạng xã hội: Tìm cầu có thể chỉ ra những mối quan hệ hoặc cá nhân đóng vai trò là "người giữ cổng" (gatekeeper) giữa các nhóm khác nhau.
• Phân tích mạch điện: Xác định các phần tử quan trọng trong mạch.

Việc xác định các cầu là một bài toán cơ bản nhưng có ứng dụng rộng rãi, và giải thuật Tarjan cung cấp một cách tiếp cận hiệu quả để giải quyết nó.

Giới Thiệu Giải Thuật Tarjan

Giải thuật Tarjan, được phát triển bởi Robert Tarjan, là một giải thuật dựa trên duyệt đồ thị theo chiều sâu (DFS). Nó nổi tiếng với khả năng tìm các thành phần liên thông mạnh (strongly connected components) trong đồ thị có hướng, nhưng ý tưởng cốt lõi và các biến thể của nó cũng cực kỳ hiệu quả trong việc tìm các tính chất khác của đồ thị, bao gồm cả việc tìm cầu và khớp nối (articulation points).

Điểm mấu chốt của Tarjan là trong quá trình DFS, nó duy trì hai thông tin quan trọng cho mỗi đỉnh u:

1. disc[u] (discovery time): Thời điểm (bước đếm) mà đỉnh u được lần đầu tiên thăm trong quá trình DFS. Chúng ta dùng một biến đếm (timer hoặc time) tăng dần sau mỗi lần gán disc.
2. low[u] (lowest reachable ancestor time): Thời điểm khám phá nhỏ nhất (minimum disc value) mà đỉnh u hoặc bất kỳ đỉnh nào trong cây con DFS gốc u có thể truy cập tới được thông qua các cạnh cây DFS và có thể sử dụng tối đa một cạnh ngược (back-edge).

Ý nghĩa của low[u] là gì? Nếu low[u] nhỏ hơn disc[u], điều đó có nghĩa là có một đường đi từ u (hoặc một đỉnh trong cây con của nó) sử dụng một cạnh ngược để quay trở lại một đỉnh đã thăm trước u trong cây DFS (một tổ tiên của u). Ngược lại, nếu low[u] == disc[u], điều đó gợi ý rằng u là "gốc" của một cấu trúc mà không có cạnh ngược nào thoát ra khỏi cây con của nó để lên phía trên u.

Ứng Dụng Tarjan Tìm Cầu

Bây giờ, làm thế nào để sử dụng hai giá trị disc và low này để tìm cầu?

Xét một cạnh (u, v) trong đồ thị, trong đó v là một đỉnh con của u trong cây DFS (nghĩa là ta đi từ u đến v lần đầu tiên trong DFS). Cạnh (u, v) là một cầu khi và chỉ khi low[v] > disc[u].

Tại sao điều kiện này lại đúng?

• disc[u] là thời điểm u được thăm.
• low[v] là thời điểm khám phá nhỏ nhất mà ta có thể đạt được từ v hoặc bất kỳ đỉnh nào trong cây con của v (bao gồm cả các cạnh ngược đi từ cây con của v).
• Nếu low[v] > disc[u], điều này có nghĩa là không có đường đi nào từ v (hoặc bất kỳ đỉnh nào trong cây con của v) mà sử dụng một cạnh ngược (hoặc kết hợp cạnh ngược với các cạnh cây) để đi tới đỉnh u hoặc bất kỳ tổ tiên nào của u. Nói cách khác, tất cả các đường đi từ cây con của v ra phần còn lại của đồ thị đều phải đi qua cạnh (u, v).
• Do đó, nếu ta loại bỏ cạnh (u, v), cây con gốc v sẽ hoàn toàn bị tách khỏi u và phần còn lại của đồ thị đã được thăm trước u, làm tăng số thành phần liên thông.

Các Bước Giải Thuật

Để áp dụng Tarjan tìm cầu, chúng ta thực hiện một quá trình DFS với các bước sau:

1. Khởi tạo các mảng disc, low, visited. Gán giá trị khởi tạo thích hợp (ví dụ: -1 cho disc, low, false cho visited).
2. Khởi tạo biến đếm thời gian timer = 0.
3. Khởi tạo một danh sách hoặc vector để lưu trữ các cầu tìm được.
4. Duyệt qua tất cả các đỉnh trong đồ thị. Nếu một đỉnh u chưa được thăm, gọi hàm DFS(u, -1) (tham số -1 biểu thị u là gốc của cây DFS hiện tại, không có đỉnh cha). Điều này đảm bảo chúng ta xử lý các thành phần liên thông khác nhau.
5. Hàm DFS(u, parent):
   • Đánh dấu u là đã thăm (visited[u] = true).
   • Gán disc[u] = low[u] = timer++.
   • Duyệt qua tất cả các đỉnh kề v của u.
     • Trường hợp 1: v là đỉnh cha (v == parent). Bỏ qua cạnh này. Đây là cạnh cây đi ngược lên cha, không phải cạnh ngược mà chúng ta dùng để cập nhật low.
     • Trường hợp 2: v đã thăm (visited[v] == true). Điều này có nghĩa (u, v) là một cạnh ngược. Cập nhật low[u]: low[u] = min(low[u], disc[v]). Chúng ta dùng disc[v] chứ không phải low[v] vì chúng ta chỉ xét một cạnh ngược trực tiếp từ u đến v.
     • Trường hợp 3: v chưa thăm (visited[v] == false). Điều này có nghĩa (u, v) là một cạnh cây.
       • Gọi đệ quy DFS(v, u).
       • Sau khi lời gọi đệ quy trả về (tức là toàn bộ cây con gốc v đã được duyệt), cập nhật low[u] dựa trên low[v]: low[u] = min(low[u], low[v]). Điều này truyền giá trị low nhỏ nhất từ cây con của v lên u.
       • Kiểm tra cầu: Nếu low[v] > disc[u], thì cạnh (u, v) là một cầu. Lưu cặp (u, v) vào danh sách cầu.

Cài Đặt Bằng C++

Chúng ta sẽ cài đặt giải thuật này bằng C++, sử dụng danh sách kề để biểu diễn đồ thị.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Các mảng và biến cần thiết cho Tarjan's Bridge Algorithm
vector<int> disc; // Thời điểm khám phá (discovery time)
vector<int> low;  // Thời điểm khám phá nhỏ nhất reachable từ đỉnh u hoặc cây con của nó
vector<bool> visited; // Đánh dấu đỉnh đã thăm
int timer; // Biến đếm thời gian
vector<pair<int, int>> bridges; // Lưu trữ các cầu tìm được

// Hàm DFS chính để tìm cầu
void bridgeDFS(int u, int parent, const vector<vector<int>>& adj) {
    // Đánh dấu u đã thăm, gán disc[u] và low[u]
    visited[u] = true;
    disc[u] = low[u] = timer++;

    // Duyệt qua tất cả các đỉnh kề v của u
    for (int v : adj[u]) {
        // Nếu v là cha của u trong cây DFS, bỏ qua
        if (v == parent) {
            continue;
        }

        // Nếu v đã được thăm (v là tổ tiên của u trong cây DFS)
        if (visited[v]) {
            // Cập nhật low[u]. Đây là một cạnh ngược.
            low[u] = min(low[u], disc[v]);
        } else {
            // Nếu v chưa được thăm (v là con của u trong cây DFS)
            // Gọi đệ quy cho v
            bridgeDFS(v, u, adj);

            // Sau khi đệ quy trả về, cập nhật low[u] dựa trên low[v]
            low[u] = min(low[u], low[v]);

            // Kiểm tra điều kiện cầu: low[v] > disc[u]
            // Nếu đúng, cạnh (u, v) là một cầu
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        }
    }
}

// Hàm wrapper để tìm cầu cho toàn bộ đồ thị
void findBridges(int n, const vector<vector<int>>& adj) {
    disc.assign(n, -1);
    low.assign(n, -1);
    visited.assign(n, false);
    timer = 0;
    bridges.clear(); // Xóa danh sách cầu cũ

    // Duyệt qua tất cả các đỉnh để đảm bảo xử lý các thành phần liên thông
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            bridgeDFS(i, -1, adj); // Bắt đầu DFS từ đỉnh chưa thăm
        }
    }
}

int main() {
    // Ví dụ 1: Đồ thị đơn giản có cầu
    // Cấu trúc: 0-1, 1-2, 2-0 (chu trình), 1-3 (cầu), 3-4
    int n1 = 5; // Số đỉnh
    vector<vector<int>> adj1(n1);
    adj1[0].push_back(1); adj1[1].push_back(0);
    adj1[1].push_back(2); adj1[2].push_back(1);
    adj1[2].push_back(0); adj1[0].push_back(2);
    adj1[1].push_back(3); adj1[3].push_back(1);
    adj1[3].push_back(4); adj1[4].push_back(3);

    cout << "Tim cau cho do thi 1:" << endl;
    findBridges(n1, adj1);
    if (bridges.empty()) {
        cout << "Khong co cau nao." << endl;
    } else {
        cout << "Cac cau tim duoc:" << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
    cout << "---" << endl;

    // Ví dụ 2: Đồ thị phức tạp hơn với nhiều chu trình
    // Cấu trúc: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3 (chu trình), 4-6 (cầu)
    int n2 = 7; // Số đỉnh
    vector<vector<int>> adj2(n2);
    adj2[0].push_back(1); adj2[1].push_back(0);
    adj2[1].push_back(2); adj2[2].push_back(1);
    adj2[2].push_back(0); adj2[0].push_back(2);
    adj2[1].push_back(3); adj2[3].push_back(1);
    adj2[3].push_back(4); adj2[4].push_back(3);
    adj2[4].push_back(5); adj2[5].push_back(4);
    adj2[5].push_back(3); adj2[3].push_back(5);
    adj2[4].push_back(6); adj2[6].push_back(4);


    cout << "Tim cau cho do thi 2:" << endl;
    findBridges(n2, adj2);
    if (bridges.empty()) {
        cout << "Khong co cau nao." << endl;
    } else {
        cout << "Cac cau tim duoc:" << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
     cout << "---" << endl;

    // Ví dụ 3: Đồ thị không có cầu
    // Cấu trúc: 0-1, 1-2, 2-0
    int n3 = 3;
    vector<vector<int>> adj3(n3);
    adj3[0].push_back(1); adj3[1].push_back(0);
    adj3[1].push_back(2); adj3[2].push_back(1);
    adj3[2].push_back(0); adj3[0].push_back(2);

    cout << "Tim cau cho do thi 3:" << endl;
    findBridges(n3, adj3);
    if (bridges.empty()) {
        cout << "Khong co cau nao." << endl;
    } else {
        cout << "Cac cau tim duoc:" << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
    cout << "---" << endl;

    return 0;
}

Giải Thích Mã Nguồn C++

Đoạn mã trên minh họa cách cài đặt giải thuật Tarjan để tìm cầu:

1. Các biến toàn cục/phạm vi hàm:

   • disc: vector<int> lưu trữ thời điểm thăm (discovery time) của mỗi đỉnh. Khởi tạo -1 để chỉ đỉnh chưa thăm.
   • low: vector<int> lưu trữ thời điểm thăm nhỏ nhất (low-link value) mà từ đỉnh hiện tại hoặc cây con của nó có thể truy cập được. Khởi tạo -1.
   • visited: vector<bool> đánh dấu đỉnh đã được thăm trong quá trình DFS hay chưa. Khởi tạo false.
   • timer: Biến đếm thời gian, tăng sau mỗi lần gán disc. Bắt đầu từ 0.
   • bridges: vector<pair<int, int>> để lưu trữ các cặp đỉnh (u, v) tạo thành một cầu.

2. Hàm bridgeDFS(int u, int parent, const vector<vector<int>>& adj):

   • Đây là hàm thực hiện quá trình duyệt đồ thị theo chiều sâu.
   • u: Đỉnh hiện tại đang xét.
   • parent: Đỉnh mà chúng ta vừa đi từ đó đến u trong cây DFS. Cần thiết để phân biệt cạnh cây đi ngược lên cha với cạnh ngược thực sự.
   • adj: Danh sách kề biểu diễn đồ thị.
   • visited[u] = true; disc[u] = low[u] = timer++;: Khi lần đầu tiên thăm u, ta đánh dấu đã thăm, gán thời điểm khám phá disc[u] và khởi tạo low[u] bằng chính disc[u]. Biến đếm timer tăng lên.
   • for (int v : adj[u]): Lặp qua tất cả các đỉnh v kề với u.
   • if (v == parent) continue;: Nếu v là đỉnh cha, bỏ qua. Ta không coi cạnh quay lại cha là một cạnh ngược ảnh hưởng đến low.
   • if (visited[v]) { low[u] = min(low[u], disc[v]); }: Nếu v đã thăm và không phải là cha, (u, v) là cạnh ngược. Ta cập nhật low[u] bằng cách lấy giá trị nhỏ nhất giữa low[u] hiện tại và disc[v]. Điều này phản ánh rằng từ u có thể đi qua cạnh ngược (u, v) đến một đỉnh đã thăm sớm hơn (disc[v]).
   • else { bridgeDFS(v, u, adj); low[u] = min(low[u], low[v]); ... }: Nếu v chưa thăm, (u, v) là cạnh cây.
     • Gọi đệ quy bridgeDFS(v, u, adj) để duyệt cây con gốc v.
     • Sau khi đệ quy trả về, cập nhật low[u] = min(low[u], low[v]). Điều này đảm bảo rằng low[u] phản ánh giá trị low nhỏ nhất có thể đạt được từ bất kỳ đỉnh nào trong cây con gốc v (bao gồm cả việc sử dụng cạnh ngược từ cây con của v).
     • if (low[v] > disc[u]) { bridges.push_back({u, v}); }: Đây là điều kiện kiểm tra cầu quan trọng nhất. Nếu thời điểm khám phá nhỏ nhất reachable từ cây con của v (low[v]) lớn hơn thời điểm khám phá của u (disc[u]), điều đó có nghĩa là không có cạnh ngược nào từ cây con của v có thể đi ngược lên u hoặc tổ tiên của u. Cạnh (u, v) chính là cầu.

3. Hàm findBridges(int n, const vector<vector<int>>& adj):

   • Hàm này là điểm khởi đầu. Nó nhận số đỉnh n và danh sách kề adj.
   • Nó khởi tạo lại các mảng disc, low, visited và biến đếm timer.
   • Nó lặp qua tất cả các đỉnh từ 0 đến n-1. Nếu một đỉnh chưa được thăm, nó gọi bridgeDFS từ đỉnh đó. Điều này đảm bảo rằng giải thuật hoạt động chính xác ngay cả với đồ thị không liên thông.

4. Hàm main():

   • Chứa các ví dụ minh họa với cấu trúc đồ thị cụ thể.
   • Tạo danh sách kề cho từng ví dụ. Lưu ý rằng với đồ thị vô hướng, nếu có cạnh (u, v), ta phải thêm cả v vào danh sách kề của u và u vào danh sách kề của v.
   • Gọi findBridges cho mỗi đồ thị.
   • In ra kết quả tìm được.

Ví Dụ Minh Họa Chi Tiết

Chúng ta hãy xem xét Ví dụ 1: Đồ thị với các cạnh (0,1), (1,2), (2,0), (1,3), (3,4).

Kết quả: Các cầu được tìm thấy là (1,3) và (3,4), đúng như mong đợi.

Độ Phức Tạp

• Thời gian: Giải thuật Tarjan dựa trên một lần duyệt DFS duy nhất. Trong quá trình DFS, mỗi đỉnh và mỗi cạnh đều được thăm một số lần hằng số. Do đó, độ phức tạp thời gian là O(V + E), trong đó V là số đỉnh và E là số cạnh. Đây là độ phức tạp tối ưu cho các giải thuật trên đồ thị phải thăm tất cả các đỉnh và cạnh.
• Không gian: Chúng ta sử dụng các mảng disc, low, visited có kích thước O(V), danh sách kề O(V + E), và stack đệ quy cho DFS có thể lên tới O(V) trong trường hợp xấu nhất (đồ thị dạng đường thẳng). Do đó, độ phức tạp không gian là O(V + E).

Bài tập ví dụ:

Giải cứu cô W

Trong một buổi nghiên cứu về dinh dưỡng, FullHouse Dev bắt gặp một câu chuyện thú vị về việc tăng cường sức mạnh thông qua việc ăn uống và nghỉ ngơi hợp lý. Điều này gợi nhớ đến câu chuyện về anh S và hành trình giải cứu cô W khỏi quái vật Lười.

Bài toán

Cô W đã bị quái vật Lười bắt cóc. Là bạn trai của cô W, anh S phải giải cứu cô ấy. Để đánh bại quái vật Lười và cứu cô W khỏi việc biến thành sinh vật lười, anh S cần đạt được một cấp độ sức mạnh nhất định.

Hiện tại, anh S đang ở cấp độ \(X\) và cần đạt đến cấp độ \(Y\). Có nhiều phương pháp chuyển đổi khác nhau:

• Nếu chọn phương pháp thứ \(i\), anh có thể chuyển từ cấp độ \(Ai\) sang cấp độ \(Bi\) với chi phí thể lực là \(Zi\) (và ngược lại).
• Tại cấp độ \(i\), anh có thể ăn Trái Ác Quỷ đặc biệt, khiến anh ngủ \(Hi\) giờ và sau đó thể lực sẽ bằng \(Ci\).

Anh S có thể chọn ăn Trái Ác Quỷ hoặc không. Có thể có nhiều cách khác nhau để di chuyển giữa các cấp độ với chi phí thời gian ngủ khác nhau.

INPUT FORMAT:

• Dòng đầu tiên chứa 4 số nguyên \(N\) (số cấp độ), \(M\) (số phương pháp chuyển đổi), \(A\) (cấp độ ban đầu), \(B\) (cấp độ cần đạt).
• \(M\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(X\), \(Y\), \(Z\), thể hiện có thể chuyển từ cấp độ \(X\) sang cấp độ \(Y\) với chi phí thể lực \(Z\).
• \(N\) dòng cuối, mỗi dòng chứa 2 số nguyên \(Ci\), \(Hi\), thể hiện tại cấp độ \(i\), có thể đạt thể lực \(Ci\) sau khi ngủ \(Hi\) giờ.

OUTPUT FORMAT:

• Một số nguyên duy nhất là thời gian ngủ tối thiểu cần thiết để đạt được cấp độ mục tiêu. Nếu không thể đạt được, in ra -1.

Ràng buộc:

• \(1 \leq N \leq 1000\)
• \(0 \leq M \leq 1000\)
• \(1 \leq \text{Cấp\_độ\_ban\_đầu}, \text{Cấp\_độ\_mục\_tiêu} \leq N\)
• \(1 \leq Xi, Yi \leq N\)
• \(1 \leq Zi \leq 10^9\)
• \(1 \leq Ci, Hi \leq 10^9\)

Ví dụ:

INPUT

3 3 1 3
1 2 2
1 3 3
3 2 1
2 7
2 7
3 6

OUTPUT

14

Giải thích:

• Đầu tiên, anh S ăn Trái Ác Quỷ ở cấp độ 1, ngủ 7 giờ và đạt thể lực 2.
• Sau đó chuyển sang cấp độ 2, tốn 2 thể lực.
• Tiếp tục ăn Trái Ác Quỷ ở cấp độ 2, ngủ 7 giờ và đạt thể lực 2.
• Cuối cùng chuyển sang cấp độ 3 với chi phí 1 thể lực.
• Tổng thời gian ngủ = 7 + 7 = 14 giờ. Hướng dẫn giải bài "Giải cứu cô W" một cách ngắn gọn:

Bài toán yêu cầu tìm thời gian ngủ tối thiểu để đi từ cấp độ A đến cấp độ B. Thời gian chỉ phát sinh khi ăn Trái Ác Quỷ (ngủ). Việc di chuyển giữa các cấp độ bằng phương pháp chuyển đổi tốn thể lực, không tốn thời gian. Thể lực được phục hồi bằng cách ngủ.

Đây là bài toán tìm đường đi ngắn nhất trên đồ thị, nơi "chi phí" cần tối thiểu hóa là thời gian ngủ.

1. Mô hình hóa:

   • Các cấp độ (1 đến N) là các đỉnh của đồ thị.
   • Có hai loại "hành động" có thể thực hiện tại một cấp độ u:
     • Ngủ: Tốn Hu thời gian ngủ, đạt Cu thể lực. Hành động này không di chuyển anh S sang cấp độ khác ngay lập tức, nhưng thay đổi trạng thái (thời gian đã ngủ, thể lực hiện có) tại cấp độ u.
     • Di chuyển: Sử dụng một phương pháp chuyển đổi từ u sang v (hoặc ngược lại) với chi phí Z. Hành động này tốn Z thể lực, không tốn thêm thời gian. Chỉ có thể thực hiện nếu anh S có đủ Z thể lực tại cấp độ u trước khi di chuyển.

2. Nhận xét quan trọng:

   • Thời gian chỉ tăng khi ngủ.
   • Thể lực là tài nguyên cần thiết cho việc di chuyển và được phục hồi bằng cách ngủ. Khi ngủ tại cấp độ i, anh S đạt Ci thể lực. Thể lực này có thể được sử dụng cho nhiều bước di chuyển liên tiếp cho đến khi anh S hết thể lực hoặc quyết định ngủ lại.
   • Khi anh S ngủ tại cấp độ u tốn Hu thời gian và đạt Cu thể lực, anh ta có thể thực hiện một chuỗi các bước di chuyển (0 thời gian) đến các cấp độ lân cận, miễn là tổng thể lực tiêu hao cho chuỗi di chuyển đó không vượt quá Cu. Bất kỳ cấp độ nào v đạt được sau chuỗi di chuyển này đều được xem là đạt được với tổng thời gian ngủ bằng thời gian đã có khi đến u cộng thêm Hu.

3. Thuật toán: Sử dụng biến thể của thuật toán Dijkstra.

   • Đỉnh của Dijkstra: Các cấp độ từ 1 đến N.
   • Trọng số đường đi: Thời gian ngủ. dist[u] là thời gian ngủ tối thiểu để đạt được cấp độ u.
   • Hàng đợi ưu tiên (Priority Queue): Chứa các cặp (thời gian, cấp độ), ưu tiên thời gian nhỏ hơn.

4. Khởi tạo:

   • Nếu cấp độ ban đầu A bằng cấp độ mục tiêu B, thời gian ngủ tối thiểu là 0. In 0 và kết thúc.
   • Khởi tạo dist[i] = INF (một giá trị rất lớn) cho tất cả các cấp độ i.
   • Cấp độ ban đầu là A. Để có thể di chuyển (nếu cần), anh S cần có thể lực. Cách duy nhất để có thể lực là ngủ. Giả sử hành động đầu tiên phải là ngủ tại cấp độ A.
   • Sau khi ngủ lần đầu tại A: thời gian là H[A], thể lực là C[A]. Từ trạng thái này, anh S có thể di chuyển đến các cấp độ khác mà tổng thể lực tiêu hao không vượt quá C[A], với thời gian là H[A].
   • Thực hiện một thuật toán tìm đường đi ngắn nhất (ví dụ: Dijkstra) phụ trên đồ thị vật lý (các phương pháp chuyển đổi) để tìm tất cả các cấp độ v có thể đạt được từ A, với tổng chi phí thể lực từ A đến v không vượt quá C[A]. Trọng số của các cạnh trong đồ thị phụ này là chi phí thể lực Z.
   • Đối với mỗi cấp độ v có thể đạt được trong bước này (với tổng thể lực tiêu hao S <= C[A]), cập nhật dist[v] = min(dist[v], H[A]). Đẩy cặp (dist[v], v) vào hàng đợi ưu tiên chính.

5. Thuật toán Dijkstra chính:

   • Trong khi hàng đợi ưu tiên chính chưa rỗng:
     • Lấy cặp (d, u) có thời gian nhỏ nhất từ hàng đợi. d là thời gian ngủ tối thiểu để đạt cấp độ u.
     • Nếu d > dist[u], bỏ qua (đã tìm thấy đường đi tốt hơn).
     • Nếu u == B, đây là thời gian ngủ tối thiểu để đạt B. In d và kết thúc thuật toán.
     • Xem xét hành động ngủ tại cấp độ u: Nếu ngủ tại u, tổng thời gian ngủ sẽ là d + H[u], và thể lực có được là C[u].
     • Từ trạng thái này (tại u, thời gian d + H[u], thể lực C[u]), anh S có thể di chuyển đến các cấp độ khác dùng thể lực C[u].
     • Thực hiện lại thuật toán tìm đường đi ngắn nhất phụ (Dijkstra) trên đồ thị vật lý bắt đầu từ u với "ngân sách" thể lực là C[u]. Mục tiêu là tìm tất cả các cấp độ v có thể đạt được từ u mà tổng chi phí thể lực từ u đến v (trong lần di chuyển này sau khi ngủ tại u) không vượt quá C[u].
     • Trọng số cạnh trong đồ thị phụ là chi phí thể lực Z. min_s_used[v] sẽ là tổng thể lực tối thiểu cần để đi từ u đến v trong lần di chuyển này.
     • Đối với mỗi cấp độ v mà min_s_used[v] không phải là INF (tức là v có thể đạt được từ u với tổng thể lực tiêu hao <= C[u]):
       • Thời gian để đạt cấp độ v thông qua việc ngủ tại u rồi di chuyển là d + H[u].
       • Nếu d + H[u] < dist[v], cập nhật dist[v] = d + H[u] và đẩy cặp (dist[v], v) vào hàng đợi ưu tiên chính.

6. Kết quả:

   • Nếu vòng lặp Dijkstra chính kết thúc mà chưa đạt được B (nghĩa là dist[B] vẫn là INF), in -1.
   • Ngược lại, in dist[B].

Lưu ý:

• Sử dụng kiểu dữ liệu long long cho thời gian, thể lực và khoảng cách để tránh tràn số.
• INF nên là một giá trị rất lớn, ví dụ 1e18.
• Thuật toán tìm đường đi ngắn nhất phụ (Dijkstra) bên trong có thể sử dụng mảng min_s_used riêng và hàng đợi ưu tiên riêng, khởi tạo lại cho mỗi lần chạy.

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