Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
A1. Mê Cung In E-mail
(6 votes)
Người viết: Ngô Minh Đức   
03/01/2009

Bài 1. Mê cung                                                                 Tên chương trình: MAZE.PAS

Một hãng tư nhân ở thành phố X vừa khánh thành một mê cung rất hấp dẫn khách du lịch. Mê cung có N phòng được đánh số từ 1 đến N và có M cầu thang, mỗi cầu thang nối trực tiếp hai phòng với nhau. Việc đi lại giữa các phòng chỉ có thể thực hiện thông qua các cầu thang. Phòng số 1 là lối vào-ra duy nhất của mê cung. Các cầu thang không cắt nhau. Giữa hai phòng bất kỳ có không quá một cầu thang nối chúng. Không có cầu thang nối một phòng với chính nó. Thời gian đi lại theo mỗi một trong hai chiều của từng cầu thang là cho trước.

Nhân dịp khai trương mê cung, chủ hãng treo giải thưởng lớn cho du khách nào có cách thâm nhập vào mê cung theo một tuyến đường nào đó trong mê cung và sau đó tìm cách thoát ra ngoài với thời gian ít nhất. Tuyến đường phải bắt đầu từ phòng số 1, đi qua ít nhất là một phòng (không kể phòng số 1) rồi quay lại phòng số 1, và thoả mãn yêu cầu: Mỗi cầu thang, mỗi phòng (không kể phòng số 1) đi qua không quá một lần.

Yêu cầu: Cho biết sơ đồ của mê cung, hãy tìm cách thâm nhập với thời gian ít nhất thoả mãn các điều kiện nêu trên.

Dữ liệu: Vào từ file văn bản MAZE.INP:

  • Dòng thứ nhất chứa hai số nguyên N (3 N 5000) và M (3 M 10000);
  • M dòng tiếp theo chứa thông tin về các cầu thang: Mỗi dòng chứa 4 số nguyên a, b, c, d được ghi cách nhau bởi dấu cách, cho biết: phòng a và phòng b được nối với nhau bởi cầu thang, và theo cầu thang này: thời gian đi từ a đến bc còn thời gian đi từ b đến ad (1 c, d 10000).

Kết quả: Ghi ra file văn bản MAZE.OUT thời gian ít nhất của cách thâm nhập tìm được.

Ví dụ:

MAZE.INP

 

MAZE.OUT

3 3

1 2 1 10

1 3 5 1

2 3 1 9

 

3

 
Tiếp >