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 hin đị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

 tải đap an tai day
Chia sẻ bài viết ^^
Other post

All comments [ 0 ]


Your comments