Một vòng quanh bang Victoria


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Victoria là một tiểu bang nhỏ thứ nhì của Úc. Nơi đây có rất nhiều địa điểm du lịch.

An đang dự định tham quan $N$ điểm du lịch. Các điểm được đánh số từ 1 đến $N$. Biết rằng, để di chuyển từ điểm thứ $i$ đến điểm thứ $j$ tốn $c_{i,j}$ đồng.

Hãy giúp An tìm một hành trình đi hết $N$ điểm sao cho chi phí bỏ ra là ít nhất.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên $N \ (0<N\le 20) $.
  • $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $c_{i,j} \ (0 \le c_{i,j} \le 10^9; c_{i,i}=0)$.

Kết quả

  • Chi phí nhỏ nhất.

Ví dụ

Ví dụ 1

input

4
0 2 4 3
2 0 5 4
1 4 0 5
8 3 1 0

output

4

Comments

There are no comments at the moment.