Hành trình với vé miễn phí
Points
68
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$. 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$
Community Discussion