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
6. Công viên Disneyland In E-mail
(4 votes)
Người viết: Ngô Minh Đức   
27/03/2008
Bờm và Cuội được mời đến vui chơi miễn phí tại công viên Disneyland nhân dịp công viên này được khai trương tại thành phố Mặt trăng. Trong công viên có tất cả n tụ điểm vui chơi (được đánh số từ 1 đến n). Trước khi đi Bờm và Cuội đã hứa sẽ chụp ảnh tất cả các tụ điểm có trong công viên để giới thiệu cho các bạn cùng lớp. Vì số lượng tụ điểm quá lớn mà thời gian lại hạn hẹp, nên Bờm và Cuội quyết định thực hiện việc dạo qua tất cả các tụ điểm để chụp ảnh theo qui tắc sau đây:
  • Cùng xuất phát tại tụ điểm 1.
  • Mỗi tụ điểm phải được ít nhất 1 người dạo qua.
  • Mỗi người sẽ thăm các tụ điểm theo thứ tự tăng dần của chỉ số.
  • Khi kết thúc, mỗi người từ tụ điểm cuối cùng trên đường đi của mình phải quay về nơi xuất phát mà không được đi qua bất cứ tụ điểm nào khác.

Yêu cầu: Cho biết tij – là thời gian đi từ tụ điểm i đến tụ điểm j (i, j = 1,2,...,n), hãy xác định giúp Bờm và Cuội cách thực hiện cách đi tuân thủ qui tắc đã nêu sao cho tổng thời gian mà hai người phải đi là nhỏ nhất.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương n.
  • Dòng thứ i trong số n dòng tiếp theo ghi các số nguyên dương ti1, ti2, ..., tin, i = 1,2, ..., n.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết qủa

In ra 1 số nguyên duy nhất là tổng thời gian nhỏ nhất tìm được.

Hạn chế

  • Trong tất cả các test: 1 ≤ n ≤ 200; tij ≤ 32000, i, j = 1,2, ..., n.
  • Có 50% số lượng test với n ≤ 100.

Ví dụ

<strong>Dữ liệu:</strong>
4 
0 1 1 3
1 0 2 8
1 2 0 6
3 8 6 0
 
<strong>Kết qủa</strong>
10

 
< Trước