Duyệt đồ thị BFS tìm đường đi ngắn nhất không trọng số
Mạng lưới máy chủ của AI Empire Academy gồm V máy chủ được đánh số từ 1 đến V và E kênh truyền thông hai chiều nối giữa các máy chủ (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105). Mỗ…
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 queue, std vector, graph representation.
Nội dung đề bài
Mục tiêu kiến thức
- Biểu diễn đồ thị vô hướng bằng danh sách kề
std::vector<std::vector<int>>. - Cài đặt thuật toán Duyệt theo chiều rộng (Breadth-First Search - BFS) bằng hàng đợi
std::queue. - Tính khoảng cách ngắn nhất (số cạnh ít nhất) từ đỉnh nguồn đến tất cả các đỉnh trong O(V + E).
- Kỹ thuật truy vết đường đi bằng mảng
parent.
Mô tả bài toán
Mạng lưới máy chủ của AI Empire Academy gồm V máy chủ được đánh số từ 1 đến V và E kênh truyền thông hai chiều nối giữa các máy chủ (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105). Mỗi kênh truyền thông có độ trễ bằng nhau (coi như trọng số bằng 1).
Cho trước máy chủ nguồn S và máy chủ đích T (1 ≤ S, T ≤ V). Bạn hãy viết chương trình:
- Tìm khoảng cách ngắn nhất (số kênh truyền ít nhất) từ S đến T. Nếu không có đường truyền nào kết nối giữa S và T, in ra
-1. - Nếu có đường đi, in ra đường đi cụ thể gồm danh sách các đỉnh từ S đến T (các đỉnh cách nhau bởi dấu cách). Nếu có nhiều đường đi ngắn nhất cùng độ dài, in ra một đường đi hợp lệ bất kỳ.
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 4 số nguyên V, E, S, T (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105, 1 ≤ S, T ≤ V).
- E dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v (1 ≤ u, v ≤ V, u ≠ v) thể hiện có kênh truyền hai chiều giữa máy chủ u và máy chủ v. Đồ thị không chứa cạnh lặp.
Output
- Nếu không có đường đi: In ra
-1. - Nếu có đường đi:
- Dòng 1: In một số nguyên là khoảng cách ngắn nhất (số cạnh).
- Dòng 2: In danh sách các đỉnh trên đường đi từ S đến T theo thứ tự, cách nhau bởi một dấu cách.
Ràng buộc
- 1 ≤ V ≤ 105.
- 0 ≤ E ≤ 2 · 105.
- 1 ≤ S, T ≤ V.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
5 5 1 5
1 2
2 3
3 5
1 4
4 5Output
2
1 4 5Giải thích
Từ đỉnh 1 đến đỉnh 5 có 2 đường đi:
- 1 → 2 → 3 → 5 (độ dài 3 cạnh).
- 1 → 4 → 5 (độ dài 2 cạnh).
Đường đi ngắn nhất có độ dài là 2 cạnh, đi qua các đỉnh 1 4 5.
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.