Đoàn người giao hàng

Buổi 33 — Bitmask DP & SOS DP
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved