Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

BCTSP2 - Travelling Salesman Problem 2

no tags 

Một người du lịch muốn tham quan n thành phố T1, …, Tn. Xuất phát từ 1 thành phố nào đó, người du lịch muốn đi qua tất cả thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay trở lại thành phố xuất phát.

Gọi C[i][j] là chi phí đi từ thành phố Ti đến Tj. Hãy tìm một hành trình thỏa mãn yêu cầu của bài toán sao cho chi phí là nhỏ nhất.

 

Lưu ý: Bài TSP 2 nhằm mục đích luyện tập cho thuật toán tham lam, thuật toán này không đảm bảo luôn tìm ra đáp án tối ưu, tuy nhiên với mục đích luyện tập test của TSP 2 được chọn để tham lam cũng tìm ra được đáp án tối ưu.

Input

Dòng đầu tiên gồm số nguyên n (0 < n <= 1000) – là số thành phố

N dòng tiếp theo, dòng thứ i nhập n số nguyên C[i][j] (0 <= j < n, 0 < C[i][j] <= 10^9) – là chi phí đi từ thành phố Ti đến Tj và ngược lại

Output

In ra chi phí nhỏ nhất có thể đạt được

Example

Input:

 

4
4 0 20 35 42 20 0 34 30 35 34 0 12 42 30 12 0
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12

 

Output: 97

Added by:adm
Date:2016-07-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY