Thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh
Hệ thống mạng lưới máy chủ vùng của AI Empire Academy gồm N trạm trung chuyển dữ liệu được đánh số từ 1 đến N (1 ≤ N ≤ 400) và M kênh kết nối một chiều (0 ≤ M ≤ 2 · 10…
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: graph representation, loops, data types.
Nội dung đề bài
Mục tiêu kiến thức
- Cài đặt thuật toán Quy hoạch động đồ thị kinh điển Floyd-Warshall với 3 vòng lặp lồng nhau O(V3).
- Trả lời nhanh Q truy vấn khoảng cách ngắn nhất giữa hai đỉnh bất kỳ trong thời gian O(1) sau khi tiền xử lý.
- Xử lý đồ thị có trọng số âm (không chứa chu trình âm) và đa cạnh giữa hai đỉnh.
- Phòng tránh tràn số khi cộng với giá trị vô cùng (
INF).
Mô tả bài toán
Hệ thống mạng lưới máy chủ vùng của AI Empire Academy gồm N trạm trung chuyển dữ liệu được đánh số từ 1 đến N (1 ≤ N ≤ 400) và M kênh kết nối một chiều (0 ≤ M ≤ 2 · 104). Tuyến cáp từ u đến v có trọng số chi phí W (-107 ≤ W ≤ 107). Đồ thị đảm bảo không chứa chu trình âm.
Sau khi nạp sơ đồ mạng, hệ thống nhận được Q truy vấn (1 ≤ Q ≤ 105), mỗi truy vấn gồm 2 trạm u và v. Hãy tìm khoảng cách ngắn nhất (tổng chi phí nhỏ nhất) từ u đến v.
Nếu không có đường đi từ u đến v, in ra -1. Khoảng cách từ một đỉnh đến chính nó luôn bằng 0 (nếu không có đường đi vòng nào tốt hơn).
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 N, M, Q (1 ≤ N ≤ 400, 0 ≤ M ≤ 2 · 104, 1 ≤ Q ≤ 105).
- M dòng tiếp theo: Mỗi dòng gồm 3 số nguyên u, v, W (1 ≤ u, v ≤ N, -107 ≤ W ≤ 107). Giữa hai đỉnh u, v có thể có nhiều cạnh, ta chọn cạnh có trọng số nhỏ nhất.
- Q dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v (1 ≤ u, v ≤ N).
Output
Gồm Q dòng, mỗi dòng in khoảng cách ngắn nhất cho truy vấn tương ứng (hoặc -1 nếu không có đường đi).
Ràng buộc
- 1 ≤ N ≤ 400.
- 0 ≤ M ≤ 2 · 104.
- 1 ≤ Q ≤ 105.
- -107 ≤ W ≤ 107.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
4 4 3
1 2 5
2 3 3
1 3 10
3 4 1
1 3
1 4
4 1Output
8
9
-1Giải thích
- Từ 1 đến 3: Đi 1 → 2 → 3 có chi phí 5 + 3 = 8 (tốt hơn cạnh trực tiếp 10).
- Từ 1 đến 4: Đi 1 → 2 → 3 → 4 có chi phí 8 + 1 = 9.
- Từ 4 đến 1: Không có đường đi → in
-1.
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.
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.