Đường Đi Ngắn Nhất Bằng Thuật Toán 0-1 BFS (0-1 BFS via Deque)
Cho một đồ thị có hướng gồm N đỉnh (đánh số từ 1 đến N) và M cung. Trọng số của mỗi cung chỉ có thể nhận một trong hai giá trị là 0 hoặc 1.
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: Standard BFS, Dijkstra Concept, std::deque.
Nội dung đề bài
Mô tả bài toán
Cho một đồ thị có hướng gồm N đỉnh (đánh số từ 1 đến N) và M cung. Trọng số của mỗi cung chỉ có thể nhận một trong hai giá trị là 0 hoặc 1.
Hãy tìm độ dài đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh 1, 2, …, N. Nếu không có đường đi từ S đến đỉnh u, khoảng cách được quy ước là -1.
Yêu cầu thuật toán đạt độ phức tạp thời gian tuyến tính O(N + M) bằng kỹ thuật 0-1 BFS.
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 đầu chứa ba số nguyên N, M, S (1 ≤ N ≤ 2 · 105, 1 ≤ M ≤ 5 · 105, 1 ≤ S ≤ N).
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w (1 ≤ u, v ≤ N, w ∈ {0, 1}) biểu diễn cung có hướng từ u đến v với trọng số w.
Output
- In ra N số nguyên trên một dòng cách nhau bởi dấu cách: khoảng cách ngắn nhất từ S đến các đỉnh 1, 2, …, N.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
4 4 1
1 2 1
2 3 0
1 3 1
3 4 1Output
0 1 1 2Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
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.