Dijkstra

// Chương trình này sử dụng c++17. Nhóm sử dụng gcc để biên dịch nên yêu cầu gcc tối thiểu 11.x (tại đây là 13.x)

#include <iostream>      
#include <fstream>       
#include <sstream>       
#include <string>        
#include <vector>       
#include <limits>        // Thư viện cho numeric_limits (ví dụ: numeric_limits<double>::max())
#include <chrono>        
#include <filesystem>    // Thư viện thao tác với hệ thống tệp (lấy tên file, thư mục, ...)
#include <algorithm>     // Thư viện chứa các hàm xử lý thuật toán (như reverse)
#include <iomanip>       // Thư viện để định dạng số khi in (std::fixed, std::setprecision)
#include <locale>        // Thư viện xử lý locale (để đọc số thực đúng với ký hiệu dấu chấm)

using namespace std;
// Sử dụng bí danh - cụ thể là: std::filesystem::path filePath = std::filesystem::current_path();
// là 1 namespace chứa các hàm, lớp để đọc/ghi tệp - yêu cầu: thư viện <filesystem>
namespace fs = std::filesystem;


// --- Cấu Trúc Dữ Liệu Pairing Heap ---


// Định nghĩa cấu trúc Node cho Pairing Heap
struct PairingHeapNode {
    double key;             // Giá trị ưu tiên (ở đây là khoảng cách, kiểu double)
    int value;              // Thông tin đỉnh, cụ thể là chỉ số của đỉnh
    PairingHeapNode* child;   // Con trỏ trỏ đến con đầu tiên của node này
    PairingHeapNode* sibling; // Con trỏ trỏ đến node anh em kế tiếp
    PairingHeapNode* parent;  // Con trỏ trỏ đến node cha (hữu ích khi dùng decreaseKey)

    // Hàm dựng: khởi tạo node với key và value cho trước, các con trỏ được khởi tạo ban đầu là nullptr.
    PairingHeapNode(double k, int val)
        : key(k), value(val), child(nullptr), sibling(nullptr), parent(nullptr) {}

    // Destructor mặc định: vì việc quản lý bộ nhớ cho cấu trúc này được thực hiện ở lớp PairingHeap.
    ~PairingHeapNode() = default;
};



// Định nghĩa lớp Pairing Heap
class PairingHeap {
public:
    PairingHeapNode* root; // Con trỏ trỏ đến nút gốc của heap

    // Constructor: khởi tạo heap rỗng, gốc được đặt là nullptr.
    PairingHeap() : root(nullptr) {}

    // Destructor: giải phóng bộ nhớ của tất cả các node còn lại trong heap khi đối tượng heap bị hủy.
    ~PairingHeap() {
        destroyHeap(root);
    }

    // Hàm destroyHeap: hàm đệ quy để giải phóng bộ nhớ các node của heap.
    // Nó duyệt theo đệ quy từ node gốc sang các node con, rồi các node anh em.
    void destroyHeap(PairingHeapNode* node) {
        if (!node) return;          // Nếu node rỗng, dừng lại
        destroyHeap(node->child);   // Giải phóng bộ nhớ cho cây con (đệ quy)
        destroyHeap(node->sibling); // Giải phóng bộ nhớ cho các node anh em
        delete node;                // Xóa node hiện tại
    }

    // Hàm merge: trộn (hoặc hợp nhất) hai cây heap h1 và h2
    // Nếu một trong hai cây rỗng, trả về cây còn lại
    // Nếu cả hai đều không rỗng, so sánh key của gốc và trả về cây có key nhỏ nhất làm gốc.
    PairingHeapNode* merge(PairingHeapNode* h1, PairingHeapNode* h2) {
        if (!h1) return h2; // Nếu h1 rỗng, trả về h2
        if (!h2) return h1; // Nếu h2 rỗng, trả về h1

        // So sánh khóa của hai gốc: nếu khóa của h1 nhỏ hơn hoặc bằng h2,
        // thì h1 trở thành gốc của cây hợp nhất.
        if (h1->key <= h2->key) {
            h2->parent = h1;          // Đặt cha của h2 là h1
            h2->sibling = h1->child;  // Gán h2 là anh em kế tiếp của con đầu tiên của h1
            h1->child = h2;           // Cập nhật con đầu tiên của h1 là h2
            return h1;                // Trả về h1 làm gốc của cây mới
        } else {
            // Nếu không, h2 có khóa nhỏ hơn, nên h2 trở thành gốc
            h1->parent = h2;          // Đặt cha của h1 là h2
            h1->sibling = h2->child;  // Gán h1 là anh em kế tiếp của con đầu tiên của h2
            h2->child = h1;           // Cập nhật con đầu tiên của h2 là h1
            return h2;                // Trả về h2 làm gốc mới
        }
    }

    // Hàm insert: chèn một node mới vào heap với giá trị key và value cho trước.
    // Tạo ra một node mới (dạng heap gồm 1 node), rồi trộn (merge) nó vào heap hiện tại.
    // Trả về con trỏ đến node vừa được chèn, để có thể dùng cho thao tác decreaseKey sau này.
    PairingHeapNode* insert(double key, int value) {
        PairingHeapNode* node = new PairingHeapNode(key, value);
        root = merge(root, node);
        if (root) root->parent = nullptr;  // Đảm bảo rằng node gốc không có cha
        return node;
    }

    // Hàm kiểm tra heap có rỗng hay không
    bool empty() const {
        return root == nullptr;
    }

    // Hàm getMin: trả về cặp {key, value} của node có key nhỏ nhất (node gốc) mà không xóa nó khỏi heap.
    pair<double, int> getMin() const {
        if (root)
            return {root->key, root->value};
        // Nếu heap rỗng, trả về cặp giá trị mặc định (key lớn nhất và value không hợp lệ)
        return {numeric_limits<double>::max(), -1};
    }

    // Hàm deleteMin: xóa node gốc (node có key nhỏ nhất) khỏi heap và trả về cặp {key, value} của nó.
    pair<double, int> deleteMin() {
        if (!root) return {numeric_limits<double>::max(), -1}; // Nếu heap rỗng

        PairingHeapNode* oldRoot = root;             // Lưu lại node gốc cũ để giải phóng bộ nhớ sau
        pair<double, int> ret = {root->key, root->value}; // Lưu giá trị trả về

        // Nếu node gốc không có con, sau khi xóa heap sẽ rỗng.
        if (!root->child) {
            root = nullptr;
        } else {
            // Nếu có con, thực hiện merge các cây con của gốc theo quy tắc merge theo cặp (two-pass merge)
            root = mergePairs(root->child);
            if (root) root->parent = nullptr; // Đảm bảo node gốc mới không có cha
        }

        delete oldRoot; // Giải phóng bộ nhớ của node gốc cũ
        return ret;     // Trả về cặp {key, value} của node đã xóa
    }

    // Hàm mergePairs: hợp nhất các node anh em theo cặp (được sử dụng trong deleteMin)
    // Đầu vào là con trỏ tới danh sách các anh em cần merge.
    // Nếu danh sách rỗng hoặc chỉ có một node, trả về node đó.
    // Nếu có nhiều hơn một node, thực hiện merge theo cặp sau đó merge kết quả.
    PairingHeapNode* mergePairs(PairingHeapNode* firstSibling) {
        if (!firstSibling) return nullptr; // Nếu danh sách rỗng, trả về nullptr
        if (!firstSibling->sibling) {
             firstSibling->parent = nullptr; // Nếu chỉ có một node, đảm bảo nó không có cha
             return firstSibling;
        }

        // Đặt 2 node đầu tiên của danh sách làm cặp a và b
        PairingHeapNode* a = firstSibling;
        PairingHeapNode* b = firstSibling->sibling;
        PairingHeapNode* rest = b->sibling; // Phần còn lại của danh sách anh em

        // Ngắt kết nối a và b với danh sách ban đầu:
        a->sibling = nullptr; 
        a->parent = nullptr;
        b->sibling = nullptr;
        b->parent = nullptr;

        // Merge cặp đầu tiên (a và b) thành một cây mới.
        PairingHeapNode* merged_ab = merge(a, b);
        // Đệ quy merge phần còn lại của danh sách.
        PairingHeapNode* merged_rest = mergePairs(rest);

        // Merge kết quả của merge cặp đầu tiên với kết quả của phần còn lại.
        return merge(merged_ab, merged_rest);
    }

    // Hàm decreaseKey: giảm khóa (key) của một node đã cho xuống giá trị newKey.
    // Điều kiện: newKey phải nhỏ hơn key hiện tại của node.
    // Sau khi giảm khóa, ta cần tách node ra khỏi vị trí cũ của nó trong cây rồi trộn vào heap lại.
    void decreaseKey(PairingHeapNode* node, double newKey) {
        if (!node || newKey >= node->key) {
            return; // Nếu node rỗng hoặc newKey không nhỏ hơn key cũ, không làm gì cả.
        }

        // Cập nhật giá trị key mới cho node.
        node->key = newKey;

        // Nếu node là gốc, việc giảm khóa chỉ cần cập nhật giá trị key.
        if (node == root) {
            return;
        }

        // --- Bước tách node khỏi cây hiện tại ---
        PairingHeapNode* nodeParent = node->parent;
        if (nodeParent != nullptr) {
            // Kiểm tra nếu node là con đầu tiên của cha
            if (nodeParent->child == node) {
                nodeParent->child = node->sibling; // Cập nhật con của cha là node kế tiếp
            } else {
                // Nếu node không phải con đầu tiên, tìm node đứng ngay trước node đó trong danh sách con của cha.
                PairingHeapNode* prevSibling = nodeParent->child;
                while (prevSibling != nullptr && prevSibling->sibling != node) {
                    prevSibling = prevSibling->sibling;
                }
                if (prevSibling != nullptr) {
                    prevSibling->sibling = node->sibling; // Loại bỏ node khỏi danh sách anh em
                }
            }
        }
        // Ngắt kết nối node hoàn toàn (không có cha, không có anh em)
        node->parent = nullptr;
        node->sibling = nullptr;

        // --- Trộn node đã được tách vào heap chính ---
        root = merge(root, node);
        if (root) root->parent = nullptr; // Đảm bảo lại node gốc không có cha
    }
};



// --- Thuật Toán Dijkstra sử dụng Pairing Heap ---
//
// Hàm dijkstra tính khoảng cách ngắn nhất từ đỉnh start đến tất cả các đỉnh khác của đồ thị.
// Đồ thị được biểu diễn dưới dạng danh sách kề (vector các vector chứa cặp {đỉnh_kề, trọng_số}).
// Kết quả được trả về qua tham chiếu ở vector dist (khoảng cách) và prev (đỉnh đi trước dùng để tái tạo đường đi).
//
void dijkstra(const vector<vector<pair<int, double>>>& graph,
              int start,
              vector<double>& dist,
              vector<int>& prev)
{
    int n = graph.size();  // Số lượng đỉnh của đồ thị

    // Khởi tạo vector dist và prev:
    // - dist: tất cả các khoảng cách ban đầu được gán là vô cùng (numeric_limits<double>::max())
    // - prev: tất cả các đỉnh trước được gán là -1 (chưa xác định)
    dist.assign(n, numeric_limits<double>::max());
    prev.assign(n, -1);

    // Đặt khoảng cách từ đỉnh start đến chính nó là 0
    dist[start] = 0.0;

    // Tạo một Pairing Heap rỗng để sử dụng trong thuật toán
    PairingHeap heap;
    // Vector heapNodes sẽ lưu các con trỏ đến các node trong heap, để thuận tiện cho việc gọi decreaseKey
    vector<PairingHeapNode*> heapNodes(n, nullptr);

    // Chèn tất cả các đỉnh vào heap:
    // - Đỉnh start có khoảng cách ban đầu 0.0
    // - Các đỉnh khác có khoảng cách ban đầu là vô cùng
    for (int i = 0; i < n; i++) {
        if (i == start)
            heapNodes[i] = heap.insert(0.0, i);
        else
            heapNodes[i] = heap.insert(numeric_limits<double>::max(), i);
    }

    // Vòng lặp chính của Dijkstra: chạy đến khi heap rỗng.
    while (!heap.empty()) {
        // Lấy đỉnh u có khoảng cách d nhỏ nhất (node gốc của heap) và xóa nó khỏi heap.
        auto [d, u] = heap.deleteMin();

        // Nếu d là vô cùng, nghĩa là các đỉnh còn lại không thể tiếp cận được từ start -> dừng thuật toán.
        if (d >= numeric_limits<double>::max() - 1.0)
            break;

        // Kiểm tra tối ưu: nếu khoảng cách d lấy ra lớn hơn khoảng cách đã biết tốt nhất (dist[u]) thì bỏ qua.
        if (d > dist[u] && dist[u] != numeric_limits<double>::max()) {
            continue;
        }

        // Duyệt qua tất cả các cạnh xuất phát từ đỉnh u.
        for (const auto& edge : graph[u]) {
            int v = edge.first;         // Lấy đỉnh kề
            double weight = edge.second;  // Lấy trọng số của cạnh (u, v)

            // --- Bước "Relaxation" (Nới lỏng cạnh) ---
            // Kiểm tra xem qua đỉnh u có cho đường đi ngắn hơn đến v không.
            // Cần đảm bảo dist[u] không phải vô cùng trước khi cộng với weight.
            if (dist[u] != numeric_limits<double>::max() && dist[u] + weight < dist[v]) {
                // Nếu tìm thấy đường đi ngắn hơn:
                // 1. Cập nhật khoảng cách từ start đến v
                dist[v] = dist[u] + weight;
                // 2. Ghi nhận đỉnh u là đỉnh đi trước của v trên đường đi ngắn nhất vừa tìm được
                prev[v] = u;
                // 3. Gọi hàm decreaseKey trên node tương ứng với đỉnh v trong heap
                heap.decreaseKey(heapNodes[v], dist[v]);
            }
        }
    }
}


// Hàm reconstruct_path: tái tạo đường đi ngắn nhất từ đỉnh start đến đỉnh end
// Dựa vào vector prev được cập nhật trong thuật toán Dijkstra.
vector<int> reconstruct_path(int start, int end, const vector<int>& prev) {
    vector<int> path;  // Vector lưu trữ các đỉnh tạo thành đường đi (đầu tiên theo thứ tự đảo ngược)
    int current = end; // Bắt đầu từ đỉnh kết thúc

    // Duyệt ngược từ đỉnh end về đến đỉnh start
    while (current != -1) {
        path.push_back(current); // Thêm đỉnh hiện tại vào đường đi
        if (current == start)    // Nếu đã về đến đỉnh start, dừng vòng lặp
            break;
        current = prev[current]; // Di chuyển sang đỉnh đi trước
    }

    // Kiểm tra xem đường đi có hợp lệ không: nếu vector path rỗng hoặc đỉnh cuối cùng không phải start thì trả về rỗng.
    if (path.empty() || path.back() != start) {
        return {}; // Không tìm thấy đường đi hợp lệ
    }

    // Vì path được lưu theo thứ tự ngược (từ end về start), ta đảo ngược lại trước khi trả về
    reverse(path.begin(), path.end());
    return path;
}



// --- Hàm Main ---
//
// Trong hàm main, chương trình thực hiện các bước sau:
// 1. Liệt kê các file .txt trong thư mục hiện hành và cho phép người dùng chọn file.
// 2. Đọc dữ liệu từ file theo định dạng: dòng đầu tiên là số đỉnh, các dòng sau là thông tin cạnh
//    theo định dạng "u, v, w" (các giá trị cách nhau bởi dấu phẩy).
// 3. Xây dựng đồ thị dưới dạng danh sách kề.
// 4. Nhập vào đỉnh bắt đầu và đỉnh kết thúc từ bàn phím.
// 5. Thực hiện thuật toán Dijkstra và đo thời gian thực hiện (nếu người dùng yêu cầu).
// 6. Tái tạo và in ra đường đi ngắn nhất cùng khoảng cách tổng.
int main() {
    // In lời chào
    cout << "============================================\n";
    cout << "   Chuong trinh tim duong di ngan nhat\n";
    cout << " Su dung thuat toan Dijkstra & Pairing Heap\n";
    cout << "============================================\n";

    // ---- Phần liệt kê và chọn file ----
    vector<string> txtFiles; // Vector lưu tên các file .txt có trong thư mục hiện hành
    vector<fs::path> txtFilePaths; // Lưu đường dẫn đầy đủ của file
    try {
        cout << "Dang quet thu muc hien tai (" << fs::current_path().string() << ") de tim file .txt...\n";
        // Duyệt qua tất cả các mục trong thư mục hiện hành
        for (const auto& entry : fs::directory_iterator(fs::current_path())) {
            // Kiểm tra nếu đây là file thông thường và có phần mở rộng là .txt
            if (entry.is_regular_file() && entry.path().extension() == ".txt") {
                // Lấy tên file (không bao gồm đường dẫn) và thêm vào vector
                txtFiles.push_back(entry.path().filename().string());
                txtFilePaths.push_back(entry.path()); // Lưu đường dẫn đầy đủ
            }
        }
    } catch (const fs::filesystem_error& e) {
        // Nếu có lỗi truy cập thư mục, thông báo nhưng vẫn cho phép nhập đường dẫn thủ công
        cerr << "Loi khi truy cap thu muc hien tai: " << e.what() << endl;
        cerr << "Ban van co the nhap duong dan file truc tiep.\n";
    }

    string fileName = ""; // Biến lưu tên file hoặc đường dẫn file được chọn

    // Chỉ hiển thị danh sách nếu tìm thấy file
    if (!txtFiles.empty()) {
        cout << "\nDanh sach file .txt tim thay:" << endl;
        for (size_t i = 0; i < txtFiles.size(); ++i) {
            cout << i + 1 << ": " << txtFiles[i] << endl;
        }
        cout << "\nChon file bang cach nhap so thu tu, hoac nhap duong dan day du toi file: ";
    } else {
        cout << "\nKhong tim thay file .txt nao trong thu muc hien tai." << endl;
        cout << "Vui long nhap duong dan day du toi file du lieu: ";
    }

    string userInput;
    // Sử dụng getline để đọc cả dòng, cho phép đường dẫn chứa khoảng trắng
    // >> ws để bỏ qua các khoảng trắng/newline còn sót lại từ các lệnh cin trước (nếu có)
    getline(cin >> ws, userInput);

    bool fileSelected = false; // Cờ để kiểm tra xem file đã được chọn hợp lệ chưa

    // Thử xử lý input như một số thứ tự
    try {
        size_t charsProcessed; // Biến để kiểm tra xem stoi có xử lý toàn bộ chuỗi không
        int choice = stoi(userInput, &charsProcessed);

        // Kiểm tra xem toàn bộ chuỗi nhập vào có phải là số không và số đó có hợp lệ không
        if (charsProcessed == userInput.length()) {
            if (choice >= 1 && choice <= static_cast<int>(txtFiles.size())) {
                // Lựa chọn số hợp lệ
                fileName = txtFilePaths[choice - 1].string(); // Lấy đường dẫn đầy đủ từ vector paths
                cout << "=> Da chon file tu danh sach: " << txtFiles[choice - 1] << " (" << fileName << ")" << endl;
                fileSelected = true;
            } else if (!txtFiles.empty()) {
                // Số nhập vào không nằm trong phạm vi danh sách
                cout << "=> Lua chon so thu tu khong hop le." << endl;
                // Không đặt fileSelected = true, sẽ rơi vào trường hợp xử lý như đường dẫn
            }
            // Nếu txtFiles rỗng, việc nhập số cũng sẽ được coi là đường dẫn
        }
        // Nếu charsProcessed != userInput.length(), nghĩa là chuỗi không hoàn toàn là số (vd: "1abc")
        // -> sẽ rơi vào khối catch hoặc xử lý như đường dẫn bên dưới.

    } catch (const std::invalid_argument&) {
        // Không phải là số -> Chắc chắn là đường dẫn
    } catch (const std::out_of_range&) {
        // Số quá lớn -> Coi như đường dẫn (ít khả năng xảy ra)
    }

    // Nếu không chọn được file từ số thứ tự, coi userInput là đường dẫn
    if (!fileSelected) {
        fileName = userInput; // Gán trực tiếp input làm tên file/đường dẫn
        cout << "=> Dang xu ly '" << fileName << "' nhu mot file." << endl;
        fileSelected = true; // Tạm thời coi là đã chọn, sẽ kiểm tra tồn tại sau
    }

    // --- Kiểm tra sự tồn tại và mở file ---
    if (!fileSelected || fileName.empty()) {
        cout << "Chua chon file nao hop le. Thoat chuong trinh." << endl;
        return 1;
    }

    // Kiểm tra xem đường dẫn file có tồn tại và là file thông thường không
    try {
        if (!fs::exists(fileName)) {
            cout << "Loi: File hoac duong dan '" << fileName << "' khong ton tai." << endl;
            return 1;
        }
        if (!fs::is_regular_file(fileName)) {
            cout << "Loi: Duong dan '" << fileName << "' khong phai la mot file thong thuong." << endl;
            return 1;
        }
    } catch (const fs::filesystem_error& e) {
        cerr << "Loi khi kiem tra file: " << e.what() << endl;
        return 1;
    }

    // Mở file để đọc dữ liệu
    ifstream infile(fileName);
    if (!infile) {
        cout << "Khong mo duoc file: " << fileName << endl;
        return 1;
    }
    cout << "Mo file '" << fileName << "' thanh cong\n";

    // ---- Phần đọc file và xây dựng đồ thị ----

    // Đọc dòng đầu tiên của file: chứa số đỉnh của đồ thị.
    string line;
    int n = 0;  // Khởi tạo số lượng đỉnh là 0.
    if (getline(infile, line)) {
        try {
            n = stoi(line); // Chuyển đổi dòng đọc được thành số nguyên.
        } catch (const std::invalid_argument& e) {
            cout << "Dinh dang file khong hop le. Dong dau tien phai la so nguyen (so dinh)." << endl;
            return 1;
        } catch (const std::out_of_range& e) {
            cout << "So dinh qua lon." << endl;
            return 1;
        }
    } else {
        cout << "File trong hoac khong doc duoc dong dau tien." << endl;
        return 1;
    }

    // Kiểm tra số đỉnh phải là số dương.
    if (n <= 0) {
        cout << "So dinh phai la so duong." << endl;
        return 1;
    }

    // Khởi tạo đồ thị dưới dạng danh sách kề:
    // Mỗi phần tử của vector graph là một vector chứa các cặp {đỉnh kề, trọng số (double)}
    vector<vector<pair<int, double>>> graph(n);

    int lineNum = 1; // Biến đếm số dòng (dùng để báo lỗi nếu có)
    // "u, v, w" với: u - đỉnh xuất phát, v - đỉnh đích, w - trọng số (số thực)
    while (getline(infile, line)) {
        lineNum++;  // Tăng số đếm dòng
        // Bỏ qua các dòng rỗng hoặc dòng comment (dòng bắt đầu bằng '#' có thể là chú thích)
        if (line.empty() || line[0] == '#') {
            continue;
        }

        // Sử dụng lambda để xóa các khoảng trắng dư thừa ở đầu và cuối chuỗi
        auto trim = [&](string &s) {
            while (!s.empty() && isspace((unsigned char)s.front())) s.erase(s.begin());
            while (!s.empty() && isspace((unsigned char)s.back())) s.pop_back();
        };
        trim(line);
        if (line.empty()) continue;

        // Tách chuỗi theo dấu phẩy: sử dụng stringstream và hàm getline với dấu phân cách là dấu ','
        vector<string> tokens;
        {
            string token;
            stringstream ss(line);
            // Đặt locale của stringstream thành "C" để đảm bảo dấu chấm ('.') được xử lý đúng
            ss.imbue(locale("C"));
            while (getline(ss, token, ',')) {
                trim(token);  // Loại bỏ các khoảng trắng dư thừa xung quanh token
                tokens.push_back(token);
            }
        }

        // Kiểm tra: dòng phải có đủ 3 trường (u, v, w)
        if (tokens.size() < 3) {
            cerr << "Canh bao: Dinh dang dong " << lineNum 
                 << " khong dung (can 3 truong u,v,w). Bo qua dong: \"" << line << "\"\n";
            continue;
        }

        // Biến tạm để lưu giá trị của u, v, và w sau khi chuyển đổi
        int u, v;
        double w;
        try {
            u = stoi(tokens[0]);  // Chuyển token đầu tiên thành số nguyên (đỉnh u)
            v = stoi(tokens[1]);  // Chuyển token thứ hai thành số nguyên (đỉnh v)
            w = stod(tokens[2]);  // Chuyển token thứ ba thành số thực (trọng số w)
        } catch (...) {
            cerr << "Canh bao: Khong the chuyen doi u,v,w o dong " << lineNum 
                 << ". Bo qua dong.\n";
            continue;
        }

        // Kiểm tra tính hợp lệ của chỉ số đỉnh: phải nằm trong khoảng [0, n-1]
        if (u < 0 || u >= n || v < 0 || v >= n) {
            cerr << "Canh bao: Dinh khong hop le o dong " << lineNum 
                 << " (u=" << u << ", v=" << v << "). Dinh phai trong khoang [0, " << n-1 << "]. Bo qua canh nay.\n";
            continue;
        }

        // Cảnh báo nếu trọng số âm (chú ý: Dijkstra không đảm bảo đúng với trọng số âm)
        if (w < 0) {
            cerr << "Canh bao: Trong so am o dong " << lineNum 
                 << " (w=" << w << "). Dijkstra co the cho ket qua sai. Dang tiep tuc xu ly...\n";
        }

        // Thêm cạnh vào đồ thị.
        // Trong ví dụ này, đồ thị được coi là có hướng: thêm cạnh từ đỉnh u đến đỉnh v với trọng số w.
        graph[u].push_back({v, w});

        // Nếu đồ thị là vô hướng, bạn có thể mở comment dòng sau:
        // graph[v].push_back({u, w});
    }
    // ***** HẾT PHẦN THAY ĐỔI ĐỌC DỮ LIỆU *****

    // Đóng file sau khi đọc xong
    infile.close();

    // ---- Nhập đỉnh bắt đầu và đỉnh kết thúc để tính đường đi ---
    int start = -1, end = -1;
    cout << "\nNhap dinh bat dau (0-" << n - 1 << "): ";
    // Lặp cho đến khi người dùng nhập đúng định dạng và nằm trong khoảng cho phép.
    while (!(cin >> start) || start < 0 || start >= n) {
        cout << "Dinh bat dau khong hop le. Vui long nhap lai (0-" << n - 1 << "): ";
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    // Yêu cầu nhập đỉnh kết thúc.
    // Người dùng có thể nhập số hay ký hiệu '#' (mặc định đặt đỉnh kết thúc là đỉnh cuối cùng n-1)
    cout << "Nhap dinh ket thuc (0-" << n - 1 << ", nhap '#' de su dung dinh " << n - 1 << "): ";
    string destInput;
    while(true) {
        cin >> destInput;
        if (destInput == "#") {
            end = n - 1;
            break;
        } else {
            try {
                end = stoi(destInput);
                if (end >= 0 && end < n) {
                    break;
                } else {
                    cout << "Dinh ket thuc ngoai pham vi. Vui long nhap lai (0-" << n - 1 << " hoac '#'): ";
                }
            } catch (...) {
                cout << "Dau vao khong hop le. Vui long nhap lai (0-" << n - 1 << " hoac '#'): ";
                cin.clear();
                cin.ignore(numeric_limits<streamsize>::max(), '\n');
            }
        }
    }

    // Hỏi người dùng có muốn hiển thị thời gian thực hiện của thuật toán Dijkstra hay không.
    // cout << "Ban co muon kiem tra hieu suat thuat toan khong? (y/n): ";
    //char perfChoice;
    //cin >> perfChoice;
    //bool checkPerf = (perfChoice == 'y' || perfChoice == 'Y');

    // ---- Thực hiện thuật toán Dijkstra và đo thời gian ----
    vector<double> dist; // Vector lưu khoảng cách ngắn nhất từ đỉnh start đến các đỉnh khác
    vector<int> prev;    // Vector lưu đường đi (đỉnh đi trước của mỗi đỉnh)

    // Lấy thời điểm bắt đầu thực hiện thuật toán
    auto startTime = chrono::high_resolution_clock::now();
    dijkstra(graph, start, dist, prev);
    // Lấy thời điểm kết thúc thực hiện thuật toán
    auto endTime = chrono::high_resolution_clock::now();
    // Tính thời gian thực hiện tính theo milli giây
    double duration = chrono::duration<double, milli>(endTime - startTime).count();

    // Nếu người dùng chọn hiển thị thời gian, in ra kết quả.
    // if (checkPerf) {
    //     cout << "Thoi gian thuc hien thuat toan: " 
    //          << fixed << setprecision(4) << duration << " ms" << endl;
    // }

    // ---- In kết quả đường đi ----
    // Kiểm tra nếu không tìm thấy đường đi từ đỉnh start đến end.
    if (dist[end] >= numeric_limits<double>::max() - 1.0) {
        cout << "\nKhong tim thay duong di tu dinh " << start << " den dinh " << end << "." << endl;
    } else {
        // Nếu tìm thấy, tái tạo đường đi bằng cách duyệt ngược vector prev.
        vector<int> path = reconstruct_path(start, end, prev);

        if (path.empty()) {
            cout << "\nKhong the tai tao duong di tu dinh " << start << " den dinh " << end << " (co the dinh ket thuc khong toi duoc hoac loi logic)." << endl;
        } else {
            // In ra đường đi ngắn nhất tìm được:
            cout << "\nDuong di ngan nhat tu dinh " << start << " den dinh " << end << ":" << endl;
            for (size_t i = 0; i < path.size(); ++i) {
                cout << path[i];
                if (i < path.size() - 1) {
                    cout << " -> ";
                }
            }
            // In tổng khoảng cách của đường đi đó với định dạng số thực (2 chữ số sau dấu phẩy)
            cout << "\n\nTong khoang cach: " 
                 << fixed << setprecision(2) << dist[end] << endl;
        }
    }

    std::cout << "\n";

    return 0; // Kết thúc chương trình thành công.
}