#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 21;
const int inf = 1 << MAXN;
int dp[inf]; // dp(pos, not yet schedded (is 1))
int n, k;
int c[MAXN][MAXN];
int ans = inf;
int solve(int mask) {
//cout << mask << endl;
if (__builtin_popcount(mask) == k) return 0;
if (dp[mask] != -1) return dp[mask];
dp[mask] = inf;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) == 0) continue;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
if ((mask & (1 << j)) == 0) continue;
dp[mask] = min(dp[mask], solve(mask ^ (1 << i)) + c[i][j]);
}
}
return dp[mask];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> c[i][j];
}
}
cout << solve((1 << n) - 1) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8396 KB |
Output is correct |
2 |
Correct |
5 ms |
8396 KB |
Output is correct |
3 |
Correct |
5 ms |
8396 KB |
Output is correct |
4 |
Correct |
5 ms |
8524 KB |
Output is correct |
5 |
Correct |
12 ms |
8524 KB |
Output is correct |
6 |
Correct |
24 ms |
8396 KB |
Output is correct |
7 |
Correct |
43 ms |
8504 KB |
Output is correct |
8 |
Correct |
96 ms |
8500 KB |
Output is correct |
9 |
Correct |
1061 ms |
8516 KB |
Output is correct |
10 |
Correct |
101 ms |
8396 KB |
Output is correct |