Thuật toán Dijkstra tìm đường đi ngắn nhất có trọng số
Hệ thống mạng lưới truyền tải mô hình trọng số lớn của AI Empire Academy gồm V trung tâm dữ liệu đánh số từ 1 đến V và E tuyến cáp quang một chiều (1 ≤ V ≤ 105, 0 ≤ E ≤ 2…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: std priority queue, std vector, graph representation.
Nội dung đề bài
Mục tiêu kiến thức
- Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị có hướng trọng số không âm bằng Min-Heap
std::priority_queue. - Đạt độ phức tạp thời gian O((V + E) log V) tối ưu.
- Kỹ thuật bỏ qua trạng thái không tối ưu (
if (d > dist[u]) continue;). - Sử dụng kiểu dữ liệu 64-bit
long longcho mảng khoảng cách tránh tràn số.
Mô tả bài toán
Hệ thống mạng lưới truyền tải mô hình trọng số lớn của AI Empire Academy gồm V trung tâm dữ liệu đánh số từ 1 đến V và E tuyến cáp quang một chiều (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105). Tuyến cáp từ u đến v có độ trễ truyền tải là số nguyên không âm W micro-giây (0 ≤ W ≤ 109).
Cho biết trung tâm phát dữ liệu gốc S (1 ≤ S ≤ V). Hãy tính khoảng cách ngắn nhất (tổng độ trễ nhỏ nhất) từ S đến tất cả các trung tâm dữ liệu từ 1 đến V.
Nếu không thể truyền tin từ S đến trung tâm i, khoảng cách được quy ước là -1.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 3 số nguyên V, E, S (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105, 1 ≤ S ≤ V).
- E dòng tiếp theo: Mỗi dòng gồm 3 số nguyên u, v, W (1 ≤ u, v ≤ V, 0 ≤ W ≤ 109) đại diện cho tuyến cáp một chiều từ u đến v có độ trễ W. Đồ thị có thể có nhiều cạnh giữa cùng một cặp đỉnh hoặc cạnh khuyên.
Output
In trên một dòng gồm V số nguyên cách nhau bởi dấu cách, số thứ i là khoảng cách ngắn nhất từ S đến i (hoặc -1).
Ràng buộc
- 1 ≤ V ≤ 105.
- 0 ≤ E ≤ 2 · 105.
- 0 ≤ W ≤ 109.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
4 4 1
1 2 5
2 3 10
1 3 20
3 4 2Output
0 5 15 17Giải thích
- Đến 1: 0.
- Đến 2: 1 → 2 (độ trễ 5).
- Đến 3: 1 → 2 → 3 (độ trễ 5 + 10 = 15, tốt hơn đi thẳng 1 → 3 với độ trễ 20).
- Đến 4: 1 → 2 → 3 → 4 (độ trễ 15 + 2 = 17).
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Ý tưởng chính & Kiến thức cốt lõi: Thuật toán Dijkstra với hàng đợi ưu tiên
Thuật toán kinh điển nhất trong lý thuyết đồ thị và ứng dụng thực tế trong hệ thống định vị GPS, định tuyến mạng Internet.
- Chỉ áp dụng cho đồ thị có trọng số không âm.
- Sử dụng priority_queue<pair<long long, int>, vector<...>, greater<...>> để lấy đỉnh có khoảng cách nhỏ nhất trong O(log V).
- Bỏ qua đỉnh đã được xử lý bằng điều kiện d > dist[u].
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.