Hành Trình TSP Có Đường Cấm

Buổi 75-76 — Stress Test
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho $N$ thành phố và ma trận chi phí đi lại có hướng $W$, trong đó $W_{ij} = -1$ nghĩa là không có đường đi trực tiếp từ $i$ đến $j$, ngược lại $W_{ij} \ge 0$ là chi phí. Hãy tìm chi phí nhỏ nhất để đi từ thành phố $1$, thăm mỗi thành phố khác đúng $1$ lần rồi quay về thành phố $1$. Nếu không thể, in -1.

Chú ý: Nếu $N = 1$, chi phí là 0.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 15$).
  • $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $W_{ij}$ ($W_{ij} = -1$ hoặc $0 \le W_{ij} \le 10^9$).
Dữ liệu ra
  • In ra một số nguyên duy nhất là chi phí nhỏ nhất hoặc -1.
Ví dụ
Input Output
1
-1
0
Giới hạn
  • $1 \le N \le 15$, $W_{ij} = -1$ hoặc $0 \le W_{ij} \le 10^9$
Draft saved