Hành Trình TSP Có Đường Cấm
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion