//
you're reading...
00 - Chủ đề chung

007. ĐÔI BẠN

Trước kia Tuấn và Mai là hai bạn cùng lớp còn bây giờ hai bạn học khác trường nhau. Cứ mỗi sáng, đúng 6 giờ cả hai đều đi từ nhà tới trường của mình theo con đường mất ít thời gian nhất (có thể có nhiều con đường đi mất thời gian bằng nhau và đều ít nhất). Nhưng hôm nay, hai bạn muốn gặp nhau để bàn việc họp lớp cũ nhân ngày 20-11.

Cho biết sơ đồ giao thông của thành phố gồm N nút giao thông được đánh số từ 1 đến N và M tuyến đường phố (mỗi đường phố nối 2 nút giao thông). Vị trí nhà của Mai và Tuấn cũng như trường của hai bạn đều nằm ở các nút giao thông. Cần xác định xem Mai và Tuấn có cách nào đi thoả mãn yêu cầu nêu ở trên, đồng thời họ lại có thể gặp nhau ở nút giao thông nào đó trên con đường tới trường hay không ? (Ta nói Tuấn và Mai có thể gặp nhau tại một nút giao thông nào đó nếu họ đến nút giao thông này tại cùng một thời điểm). Nếu có nhiều phương án thì hãy chỉ ra phương án để Mai và Tuấn gặp nhau sớm nhất.

Dữ liệu vào được đặt trong tệp FRIEND.INP:

  • Dòng đầu tiên chứa 2 số nguyên dương N, M (1 £ N £ 100);
  • Dòng tiếp theo chứa 4 số nguyên dương Ha, Sa, Hb, Sb lần lượt là số hiệu các nút giao thông tương ứng với: Nhà Tuấn, trường của Tuấn, nhà Mai, trường của Mai.
  • Dòng thứ i trong số M dòng tiếp theo chứa 3 số nguyên dương A, B, T. Trong đó A & B là hai đầu của tuyến đường phố i. Còn T là thời gian (tính bằng giây £ 1000) cần thiết để Tuấn (hoặc Mai) đi từ A đến B cũng như từ B đến A.

Giả thiết là sơ đồ giao thông trong thành phố đảm bảo để có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại.

Kết quả : Ghi ra tệp văn bản FRIEND.OUT

  • Dòng 1: Ghi từ YES hay NO tuỳ theo có phương án giúp cho hai bạn gặp nhau hay không. Trong trường hợp có phương án:
  • Dòng 2: Ghi thời gian ít nhất để Tuấn tới trường
  • Dòng 3: Ghi các nút giao thông theo thứ tự Tuấn đi qua
  • Dòng 4: Ghi thời gian ít nhất để Mai tới trường
  • Dòng 5: Ghi các nút giao thông theo thứ tự Mai đi qua
  • Dòng 6: Ghi số hiệu nút giao thông mà hai bạn gặp nhau
  • Dòng 7: Thời gian sớm nhất tính bằng giây kể từ 6 giờ sáng mà hai bạn có thể gặp nhau.

Các số trên một dòng của Input/Output file ghi cách nhau ít nhất một dấu cách.

Ví dụ : Với sơ đồ giao thông sau: (N=6,M=7, Ha=1, Sa=6, Hb=2, Sb=5)

Dòng FRIEND.INP FRIEND.OUT
1

2

3

4

5

6

7

8

9

6 7

1 6 2 5

1 3 10

1 4 10

2 3 5

3 4 5

3 6 15

4 5 20

4 6 15

YES

25

1 4 6

30

2 3 4 5

4

10

 bai_007
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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 180,806 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: