//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Tuyến xe buýt

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 10


Đề bài


Thành phố Hà Nội vừa mới đưa vào hoạt động M tuyến xe buýt đánh số từ 1 đến M (3<= M <=10) và N bến xe buýt đánh số từ 1 đến N (20<=N<=100). Mỗi tuyến xe buýt được mô tả bởi dãy các bến mà nó đi qua. Thời gian di chuyển giữa hai bến liên tiếp trên bất cứ tuyến nào cũng là 5 phút. Thời gian để đổi từ tuyến này sang tuyến khác tại bến chung của chúng là 3 phút.

Yêu cầu: Hãy xác định cách đi với thời gian ít nhất từ bến xuất phát S tới bến đích T.

Dữ liệu: Vào từ file BUSLINE.INP:

  • Dòng đầu tiên chứa hai số M, N
  • Mỗi dòng trong M dòng tiếp theo mô tả một tuyến xe buýt. Số đầu tiên trong dòng là số lượng bến trên tuyến, tiếp đến là dãy các bến xe trên tuyến.
  • Dòng cuối cùng chứa hai số S, T.

Kết quả: Ghi ra file văn bản BUSLINE.OUT thời gian nhỏ nhất để đi từ bến S đến bến T theo các tuyến xe buýt của thành phố. Ghi -1 nếu không thể có cách đi từ S đến T.

Ví dụ:

BUSLINE.INP BUSLINE.OUT
3 11

4 1 3 7 8

5 2 3 4 5 6

4 6 11 10 9 8

4 9

26

 

Cách đi:

  • Theo tuyến 2 đi từ bến 4 đến bến 3
  • Đổi sang tuyến 1, đi từ 3 qua 7 đến 8
  • Đổi sang tuyến 3, đi từ 8 đến 9

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

To See the Light

Keep calm and eat chips.

Macro Mondays - Chip(s)

More Photos

Thống kê

  • 135,663 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: