Hành trình với vé miễn phí

Buổi 33 — Bitmask DP & SOS DP
Points
68
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$. Chi phí đi từ thành phố $i$ đến thành phố $j$ là $C[i][j]$. Một du khách xuất phát từ thành phố $1$, muốn đi qua tất cả $N$ thành phố (mỗi thành phố đúng một lần) và quay trở về thành phố $1$. Du khách có tối đa $K$ vé miễn phí; mỗi vé cho phép đi một chặng bất kỳ $(u \to v)$ trong hành trình với chi phí $0$. Hãy tìm tổng chi phí nhỏ nhất để hoàn thành hành trình.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $K$ ($2 \le N \le 14$, $0 \le K \le 3$).
  • $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^9$, $C[i][i] = 0$).
Dữ liệu ra
  • In ra tổng chi phí nhỏ nhất.
Ví dụ
Input Output
4 1
0 10 100 10
10 0 100 100
100 100 0 10
10 100 10 0
30
3 2
0 50 50
50 0 50
50 50 0
50
Giới hạn
  • $2 \le N \le 14$, $0 \le K \le 3$
  • $0 \le C[i][j] \le 10^9$
Draft saved