Đường đi ngắn nhất giữa hai đỉnh
Một nhóm bạn được mô tả bằng các cặp quen nhau. Quan hệ quen là hai chiều: nếu A quen B
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một nhóm bạn được mô tả bằng các cặp quen nhau. Quan hệ quen là hai chiều: nếu A quen B thì B cũng quen A. Ta muốn biết cần đi qua ít mối quan hệ nhất là bao nhiêu bước để từ một người tới một người khác trong nhóm.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh (đánh số từ 1 tới n) và m cạnh, cùng hai đỉnh s và t. Hãy tính số cạnh ít nhất trên một đường đi từ s tới t (đếm số cạnh, KHÔNG đếm số đỉnh). Nếu t không tới được từ s, in ra -1. Nếu s trùng t, in ra 0 vì không cần đi cạnh nào.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ hay dấu cách nào khác. Chương trình chỉ dùng thư viện chuẩn C++17 và không cần tối ưu vì dữ liệu rất nhỏ.
Input
- Dòng đầu tiên: hai số nguyên n và m (1 <= n <= 8, 0 <= m <= 12).
- m dòng tiếp theo: mỗi dòng hai số nguyên u, v (1 <= u, v <= n, u != v) cho biết
có một cạnh vô hướng nối đỉnh u với đỉnh v. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.
- Dòng cuối cùng: hai số nguyên s, t (1 <= s, t <= n).
Output
In ra stdout một số nguyên duy nhất: số cạnh ít nhất của một đường đi từ s tới t, hoặc -1 nếu không tồn tại đường đi như vậy.
Ràng buộc
- Cạnh là vô hướng, đi được theo cả hai chiều.
- Đồ thị có thể rời rạc; khi đó kết quả có thể là -1.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5 4
1 2
2 3
3 4
2 5
4 5
Output
3
Ví dụ 2
Input
4 2
1 2
3 4
1 4
Output
-1
Giải thích
Dữ liệu vào:
Đồ thị có các cạnh 1-2, 2-3, 3-4, 2-5 và cần đi từ đỉnh 4 tới đỉnh 5. Đường đi ngắn nhất là 4 -> 3 -> 2 -> 5, gồm 3 cạnh, nên kết quả là:
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.
