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.|

SSAM319C - HÀNH TRÌNH DU LỊCH

Trong kì nghỉ hè năm nay Tí được bố thưởng cho 1 tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng. Tất nhiên Tí sẽ đi bằng máy bay.

Giá vé máy bay từ đất nước i đến đất nước j là C[i][j] (dĩ nhiên C[i][j] có thể khác C[j][i]). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng Tí cũng muốn tìm cho mình 1 hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người.

Bạn hãy giúp Tí tìm 1 hành trình đi qua tất cả các nước, mỗi nước đúng 1 lần sao cho chi phí là bé nhất nhé.

Input:

Dòng đầu tiên là số lượng bộ test T (T ≤ 20).

Mỗi test bắt đầu bởi số nguyên dương N (5 ≤ N ≤ 15).

N dòng tiếp theo, mỗi dòng gồm N số nguyên mô tả chi phí C[i][j] (1≤ C[i][j] ≤ 10000).

Output: 

Với mỗi test, in ra đáp án tìm được trên một dòng.

 

Test ví dụ:

Input:

Output

1

6

0 1 2 1 3 4

5 0 3 2 3 4

4 1 0 2 1 2

4 2 5 0 4 3

2 5 3 5 0 2

5 4 3 3 1 0

 

8

 

Giải thích test: 1 hành trình tối ưu là 3à 6 à 5 à 1 à 2 à 4.

 


Được gửi lên bởi:Admin
Ngày:2019-08-02
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.