#include <bits/stdc++.h>
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
#define int long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=1e6,M=21,Mod=1e9;
int dp[1<<M],k,n,a[M][M];
int rec(int mask){
if(__builtin_popcount(mask)==k)return 0;
int &ret=dp[mask];
if(~ret)return ret;
ret=1e9;
for(int i=0;i<n;i++){
if(!(mask&(1<<i)))continue;
for(int j=0;j<n;j++){
if(i==j||!(mask&(1<<j)))continue;
ret=min(ret,rec(mask^(1<<i))+a[i][j]);
}
}
return ret;
}
void testcase(int h){
memset(dp,-1,sizeof dp);
cin>>n>>k;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
cout<<rec((1<<n)-1);
}
int32_t main()
{
// fast
testcase(1);
// int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
16716 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16596 KB |
Output is correct |
| 3 |
Correct |
8 ms |
16596 KB |
Output is correct |
| 4 |
Correct |
7 ms |
16724 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16596 KB |
Output is correct |
| 6 |
Correct |
34 ms |
16720 KB |
Output is correct |
| 7 |
Correct |
52 ms |
16700 KB |
Output is correct |
| 8 |
Correct |
103 ms |
16596 KB |
Output is correct |
| 9 |
Correct |
1246 ms |
16704 KB |
Output is correct |
| 10 |
Correct |
120 ms |
16704 KB |
Output is correct |
