//
you're reading...
Bài tập huấn luyện

Bài tập luyện tập: Các đại lý

 

Sau một số rủi ro và thất bại trong kinh doanh, tổng giám đốc công ty MPT là Mr HÙNG quyết định tổ chức cho các sếp nhỏ của các đại lý thuộc công ty gặp mặt và thảo luận với nhau. Công ty MPT là một công ty cực kì lớn trải khắp toàn cầu nên một vấn đề lớn đặt ra là làm sao tổ chức cho 2 sếp nhỏ gặp nhau trong thời gian sớm nhất. Vấn đề đặc biệt trở nên hóc búa vì các nhân viên của công ty chỉ được đi bằng mạng giao thông của công ty để đảm bảo an toàn, bảo mật và chi phí. Nhưng mạng này lại khá là … yếu kém vì:

  • Các nhân viên buộc phải di chuyển theo các tuyến giao thông giữa các đại lý.
  • Mạng giao thông của công ty là mạng gồm các tuyến đường 1 chiều.
  • Các nhân viên khi đi trong mạng thì mỗi giờ đi được theo đúng 1 tuyến đường và phải liên tục di chuyển (nghĩa là không được dừng lại).

Được cái đây là mạng nội bộ và với công nghệ đỉnh cao nên không có chuyện tắc đường. Vì vậy, trong 1 giờ luôn có thể di chuyển từ đại lý này sang đại lý khác nếu có đường.

Thời gian là vàng bạc, MHÙNG quyết không để nhân viên của mình lãng phí 1 giây nào cả. Bởi vậy ông muốn tính thời gian ngắn nhất mà 2 sếp ở 2 đại lý cho trước có thể gặp nhau. Đáng tiếc là MHÙNG chỉ giỏi kinh doanh, còn lập trình thì quá yếu kém. Bạn là nhân viên dưới quyền MHÙNG và đang rất muốn thể hiện khả năng của mình. Vậy thì, hãy nhân cơ hội này để cho MHÙNG thấy trình độ tuyệt vời của bạn.

InputAGENTS.INP

  • Dòng đầu ghi 2 số N, M là số đại lý và số tuyến đường trong mạng giao thông của công ty MPT.
  • Dòng thứ 2 ghi S,T lần lượt là số thứ tự 2 đại lý có 2 sếp cần phải gặp nhau.
  • M dòng tiếp theo mỗi dòng ghi 2 số nguyên U, V thể hiện có đường đi một chiều từ U tới V.

Output:            AGENTS.OUT

  • Gồm một dòng duy nhất ghi thời gian nhỏ nhất 2 sếp có thể gặp nhau.
  • Nếu 2 sếp không thể gặp nhau ghi -1.

Giới hạn:

  • N ≤ 250, M ≤ N × (N – 1).
  • Thời gian: 1 s/test
  • Bộ nhớ: 8 MB

Ví dụ:

AGENTS.INP AGENTS.OUT
6 7

1 5

1 2

4 5

2 3

3 4

4 1

5 4

5 6

3

 

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ả

Chuyên mục

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ê

  • 252,771 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: