Công viên Disneyland (version 2)

View as PDF

Submit solution


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

Problem source:
Từ việc hiểu nhầm đề bài DISNEY1
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 chỉ thuộc ~1~ trong ~2~ đường đi của Bờm hoặc Cuội (tất nhiên là trừ điểm số ~1~).
  • 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.