Tham gia SEGAME bằng xe buýt
Thứ Sáu, 26 tháng 6, 2015
Để phục vụ cho SEGAME 25, nước bạn
Lào của chúng ta đã chuẩn bị rất chu đáo về mọi mặt, đặc biệt là phương tiện giao
thông cho
các vận động viên cũng như khán giả. Đất nước Lào đã xây dựng hệ
thống xe buýt đi lại giữa một số địa điểm, các tuyến xe buýt đều là đường đi
hai chiều. Các hoạt động của SEGAME được tổ chức ở N địa điểm (1
£ N £ 100) các địa điểm được đánh
số từ 1 đến N. Các trạm dừng xe buýt đều được đặt ở các địa điểm tổ chức SEGAME,
tất nhiên vì điều kiện không cho phép nên có một số địa điểm không có trạm xe
buýt và giữa một số địa điểm không thể đi lại bằng xe buýt được. Em hãy giúp các
vận động viên cũng như khán giả đến cổ vũ SEGAME xác định được từ địa điểm A
đến địa điểm B nào đó có thể đi được bằng xe buýt không? Nếu đi được thì nên đi
theo tuyến như thế nào để số lần dừng lại ở các trạm xe buýt là ít nhất.
D÷ liÖu vµo: Đọc tõ file v¨n b¶n XEBUYT.INP gåm:
- Dßng ®Çu tiªn lµ sè N (1 £ N £ 100);
- Dòng thứ hai ghi hai số nguyên dương thể hiện địa điểm A và B.
- C¸c dßng tiÕp theo mçi dßng ghi hai sè i vµ j cho biÕt cã tuyến xe buýt gi÷a 2 địa điểm i vµ j.
KÕt qu¶: Ghi ra file v¨n
b¶n XEBUYT.OUT nếu không đi được ghi số -1, nếu được ghi đường đi từ A đến B qua ít trạm xe buýt nhất.
Ví
dụ:
XEBUYT.INP
|
XEBUYT.OUT
|
XEBUYT.INP
|
XEBUYT.OUT
|
9
2 3
1 3
1 6
2 7
3 6
4 8
6 7
8 9
|
2 7 6 3
|
9
3 8
1 3
1 6
2 7
3 6
4 8
6 7
8 9
|
-1
|
All comments [ 0 ]
Your comments