HSG12 Long An 2010 - Bài 2
Xem dạng PDF
Mã bài:
city
Điểm:
1,5 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Trong một quốc gia có ~N~ thành phố, đường đi giữa các thành phố là đường đi hai chiều. Giữa hai thành phố ~P~, ~Q~ khác nhau có thể có đường đi trực tiếp hoặc gián tiếp thông qua các thành phố trung gian hoặc không có đường đi để đi từ ~P~ đến ~Q~ (do ~1~ trong ~2~ thành phố bị tách biệt, có thể ngoài đảo không có đường bộ để đi).
Yêu cầu
Tìm đường đi từ thành phố ~P~ đến thành phố ~Q~ (khác ~P~) sao cho đường đi qua ít thành phố nhất (tính cả thành phố xuất phát lẫn thành phố cần đến). Các thành phố được đánh số thứ tự bắt đầu từ ~1, 2, ... , N~.
Dữ liệu vào:
- Dòng đầu tiên ghi số ~N, M, P, Q (0 < N < 100)~ lần lượt là số thành phố trong quốc gia, số đường đi hai chiều nối các thành phố với nhau, thành phố xuất phát, thành phố cần đến.
- ~M~ dòng tiếp theo, mỗi dòng chứa ~1~ cặp số nguyên dương ~S~ và ~T~ thể hiện đường đi hai chiều giữa ~2~ thành phố ~S~ và ~T~.
Kết quả ra:
Nếu có đường đi từ ~P~ đến ~Q~ thì đưa ra gồm ~2~ dòng:
- Dòng 1: ghi số thành phố ít nhất được đi qua (kể cả thành phố xuất phát và thành phố cần đến).
- Dòng 2: ghi lần lượt các thành phố được đi qua theo đường đi được tìm thấy (đường đi qua số thành phố ít nhất).
Nếu không có đường đi từ ~P~ đến ~Q~ thì ghi ~-1~.
Sample Input
5 6 1 5
1 2
1 4
2 3
2 5
3 4
4 5
Sample Output
3
1 2 5
Bình luận
This comment is hidden due to too much negative feedback. Show it anyway.
ok anh
khi nào ra đề, ad có thể thêm giới hạn đầy đủ 1 tí được ko ạ :<
Quyết Phan Ngọc
sao bạn biết tên mình thế :)
Đề tỉnh mình v á, bạn thấy bài nào thiếu báo cáo ad cập nhật
khi nào trường mình mới thi để chọn đi thi tỉnh vậy bạn
K biết bạn trường nào chứ trường của mình thi chọn 11 12 thi tỉnh r á