#include <bits/stdc++.h>
//#define int long long
using namespace std;
int const maxn = 2005,MOD=1e9 + 7;
int d[maxn];
struct road{
int a,b,cost;
};
int pow(int a,int b){
int result = 1;
while (b>0){
if (b&1) {
result *= a;
}
a = a*a;
b = b>>1;
}
return result;
}
int gcd(int a,int b){
if (b==0) return a;
if (a<b) swap(a,b);
return gcd(b,a%b);
}
int count2(int x){
return __builtin_popcount(x);
}
int count3(int x){
int cnt=0;
while (x){
if (x%3==1) cnt++;
x/=3;
}
return cnt;
}
int c[25][25];
int dp[(1<<20)]; //the minimum effort to put everything into this number of bottle
void solve(){
int n,k;cin>>n>>k;
for (int i=0;i<n;++i) for (int j=0;j<n;++j) cin >> c[i][j];
dp[(1<<n)-1] = 0;
for (int mask=(1<<n)-2;mask>0;--mask){
dp[mask] = INT_MAX;
for (int i=0;i<n;++i){
if (!(mask&(1<<i))){//ith bit is 0
for (int j=0;j<n;++j){
if (mask&(1<<j)){//jth bit' is 1
dp[mask] = min(dp[mask],dp[mask^(1<<i)] + c[i][j]);
}
}
}
}
}
int ans = INT_MAX;
for (int mask=1;mask<(1<<n);++mask){
int sz=0;
for (int i=0;i<n;++i) if ((1<<i)&mask) sz++;
if (sz==k) ans = min(dp[mask],ans);
}
cout << ans;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
7 ms |
332 KB |
Output is correct |
| 6 |
Correct |
14 ms |
452 KB |
Output is correct |
| 7 |
Correct |
31 ms |
480 KB |
Output is correct |
| 8 |
Correct |
64 ms |
708 KB |
Output is correct |
| 9 |
Correct |
612 ms |
4456 KB |
Output is correct |
| 10 |
Correct |
611 ms |
4336 KB |
Output is correct |
