Dijkstra
Sử dụng cấu trúc Pairing Heap để lưu trữ và sử lý dữ liệu. Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhấtunknown
c_cpp
16 days ago
28 kB
4
Indexable
// 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 << "Hello\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 try { // 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()); } } } catch (const fs::filesystem_error& e) { cerr << "Loi truy cap thu muc: " << e.what() << endl; return 1; } // Kiểm tra nếu không tìm thấy file .txt nào if (txtFiles.empty()) { cout << "Khong tim thay file .txt nao trong thu muc hien tai." << endl; return 1; } // In ra danh sách các file .txt vừa tìm thấy cout << "Danh sach file .txt:" << endl; for (size_t i = 0; i < txtFiles.size(); ++i) { cout << i + 1 << ": " << txtFiles[i] << endl; } // Yêu cầu người dùng chọn file bằng cách nhập số thứ tự cout << "Chon file (nhap so thu tu): "; int fileChoice; cin >> fileChoice; // Kiểm tra tính hợp lệ của lựa chọn (số nhập vào phải nằm trong phạm vi danh sách file) if (cin.fail() || fileChoice < 1 || fileChoice > static_cast<int>(txtFiles.size())) { cout << "Lua chon khong hop le." << endl; cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); return 1; } // Lấy tên file tương ứng với lựa chọn của người dùng string fileName = txtFiles[fileChoice - 1]; cout << "Da chon file: " << fileName << endl; // Mở file để đọc dữ liệu ifstream infile(fileName); if (!infile) { cout << "Khong mo duoc file: " << fileName << endl; return 1; } // ---- 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ó) // ***** THAY ĐỔI ĐOẠN NÀY: Đọc dữ liệu dạng "u, v, w" ***** // Mỗi dòng trong file (sau dòng đầu tiên) được kỳ vọng có định dạng: // "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 << "\nTong khoang cach: " << fixed << setprecision(2) << dist[end] << endl; } } return 0; // Kết thúc chương trình thành công. }
Editor is loading...
Leave a Comment