Một vòng quanh bang Victoria
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