Đoàn người giao hàng
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ thành phố đánh số từ $1$ đến $N$ và $K$ người giao hàng cùng xuất phát tại thành phố $1$. Mỗi thành phố từ $2$ đến $N$ phải được đi qua bởi đúng một người giao hàng (người giao hàng có thể không đi thành phố nào khác ngoài thành phố $1$, hoặc đi qua một tập hợp các thành phố rồi quay về $1$). Cho ma trận chi phí $C[i][j]$ từ $i$ đến $j$. Hãy tìm tổng chi phí di chuyển nhỏ nhất của cả $K$ người.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $K$ ($2 \le N \le 14$, $1 \le K \le 4$).
- $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^6$, $C[i][i] = 0$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 2 0 10 100 10 10 0 100 100 100 100 0 10 10 100 10 0 |
130 |
| 3 2 0 5 5 5 0 100 5 100 0 |
20 |
Giới hạn
- $2 \le N \le 14$
- $1 \le K \le 4$
- $0 \le C[i][j] \le 10^6$
Community Discussion