busways busways mét hö thèng c¸c xe buýt cã nhiöm vô chuyªn chë hµnh kh¸ch ®i l¹i gi÷a mét sè ga sao cho ®¶m b¶o týnh liªn th«ng hai chiòu gi÷a c¸c ga nµy hö thèng bao gåm mét sè tuyõn ®êng mçi tuyõ
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (37.5 KB, 1 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
<b>busways</b>
Một hệ thống các xe buýt có nhiệm vụ chuyên chở hành khách đi lại giữa một số
ga sao cho đảm bảo tính liên thơng hai chiều giữa các ga này. Hệ thống bao gồm một số
tuyến đờng, mỗi tuyến đờng gồm một số ga khác nhau theo thứ tự mà xe buýt đi qua. Xe
buýt thuộc tuyến đờng nào chỉ chạy trên tuyến đờng đó, lần lợt qua các ga thuộc tuyến
cho đến hết, sau đó lại quay đầu chạy theo hớng ngợc lại. Có thể có một số ga chung cho
một số tuyến đờng. Một hành khách muốn đi từ ga đầu đến ga cuối, có thể đi trên một
tuyến hoặc phải chuyển tuyến một số lần ở những nơi có ga chung. Bài tốn đặt ra là, tìm
một hành trình cho phép đi từ ga đầu đến ga cuối sao cho số lần phải chuyển tuyến là ít
nhất. Nếu tồn tại nhiều phơng án nh vậy, hãy tìm phơng án đi qua ít ga nhất.
Dữ liệu vào đợc đọc từ file văn bản, gồm:
- dòng đầu là số tuyến đờng,
- các dòng tiếp, mỗi dịng mơ tả một tuyến đờng, gồm một chuỗi ký tự viết
liền nhau, mỗi ký tự mô tả một tên ga theo đúng thứ tự của các ga trên tuyến (chú ý các
ga trên cùng một tuyến là khác nhau, nhng các ga trên các tuyến khác nhau có thể trùng
nhau, tên ga có thể là một ký tự bất kỳ hiển thị đợc trong bảng mã ASCII),
- dßng tiÕp theo là số hành trình cần tìm,
- cỏc dũng tip, mỗi dịng mơ tả một hành trình cần tìm, gồm cặp ký tự viết
liền nhau, xác định các tên ga đầu và ga cuối.
Giả thiết rằng các dữ liệu vào là hợp lệ, khơng cần kiểm tra. Giới hạn kích thớc
100 cho số các tuyến đờng và 50 cho số các ga trên một tuyến đờng.
Kết quả đa ra file văn bản, trong đó mỗi hành trình đợc viết trên một dòng, gồm
các ký tự biểu diễn tên ga viết theo thứ tự đợc đi. Các tên ga này đợc viết thành từng
nhóm theo tuyến đờng: nếu thuộc cùng một tuyến thì viết liền nhau, nếu sang tuyến khác
thì viết cách nhau một dấu trắng (space), tên ga chung đợc vit lp li.
<i>Thí dụ</i> :
File dữ liệu vào dới đây :
<i>3</i>
<i>ABC</i>
<i>DBE</i>
<i>GAEH</i>
<i>2</i>
<i>HC</i>
<i>GB</i>
mô tả một hệ thống xe buýt gồm 3 tuyến nh hình vẽ và địi hỏi tìm 2 hành trình: từ H đến
C và từ G đến B thoả mãn các yêu cầu đã nêu.
File kÕt qu¶ cho thÝ dơ nµy lµ:
<i>HEA ABC</i>
<i>GA AB</i>
trong đó dịng đầu mơ tả hành trình đi từ H đến C gồm 2 tuyến, 5 ga, dịng thứ hai mơ tả
hành trình đi từ G đến B gồm 2 tuyến, 3 ga.
A
B
C
D
E
G
</div>
<!--links-->
