Công viên Disneyland (version 1)

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Thi vòng 2 nãm 2006 và cám ơn Mr.Nguyễn Trần Nam Khánh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Công viên Disneyland khai trương ~N~ điểm vui chơi mới. Một hôm Bờm và Cuội đến chơi Công viên. Qua việc hỏi thăm người hướng dẫn Bờm và Cuội đã biết thời gian cụ thể để đi từ điểm vui chơi ~i~ đến địa điểm vui chơi ~j~. Bờm và Cuội muốn đi thăm hết tất cả các địa điểm theo nguyên tắc sau:

  • Mỗi người đi từ điểm số ~1~, qua ~1~ số điểm và quay trở về điểm số ~1~.
  • Các điểm đến trên đường đi của Bờm và Cuội là ~1~ dãy số tăng dần( trừ điểm số ~1~ khi quay về).
  • Mỗi điểm vui chơi phải thuộc ít nhất ~1~ trong ~2~ đường đi của Bờm và Cuội.
  • Thời gian đi là nhỏ nhất (tính cả thời gian quay về ~1~).

Input

  • Dòng đầu là số ~N (N < 201)~
  • Tiếp theo là ma trận ~N~ dòng ~N~ cột: ~1~ số nguyên không âm~(<1001)~ trên hàng ~i~ cột ~j~ cho ta biết thời gian đi từ địa điểm ~i~ đến địa điểm ~j~. ~(A_{i,j} = A_{j,i}, A_{i,i} = 0~ với mọi ~i, j)~.

Output

Gồm ~1~ số duy nhất là thời gian nhỏ nhất để Bờm và Cuội thăm quan Công Viên theo nguyên tắc trên.

Sample Input

4
0 1 4 3
1 0 2 4
4 2 0 4
3 4 4 0

Sample Output

10

Note

(Giải thích : cách đi tốt nhất là Bờm đi ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1~ và Cuội đứng yên).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.