#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#define endl '\n'
#define sp ' '
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn = 25;
const int inf = 1e9;
int c[maxn][maxn];
int popcount(int n){
int ret = 0;
for(int mask = 1;mask != (1<<maxn);mask<<=1){
if(n&mask)
ret++;
}
return ret;
}
int d[maxn][maxn];
int p[maxn][maxn];
void shortest(int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j) d[i][j] = 0;//inf;
else d[i][j] = c[i][j];
p[i][j] = j;
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[i][k];
}
}
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cerr << d[i][j] << sp;
}
cerr << endl;
}*/
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
int n,k;cin>>n>>k;
vector<int> mask;
for(int i=0;i<=(1<<n)-1;i++){
if(popcount(i) == k)
mask.pb(i);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>c[i][j];
}
}
shortest(n);
int ans = 1e9;
int ansmask = 0;
for(int m : mask){
int curans = 0;
int curm = m;
int minm = 0;
for(int a = 0;a<n;a++){
if(!(m & (1<<a))){
int bul = inf;//1e9;
for(int b = 0;b<n;b++){
int curbul = 0;
if(m & (1<<b)){
//bul = min(bul,d[a][b]);
curm = m;
minm = 0;
int gez = a;
while(gez != b && !(m&(1<<gez))){
curbul += d[gez][p[gez][b]];
curm |= (1<<(gez));
gez = p[gez][b];
}
if(curbul < bul){
bul = curbul;
minm = curm;
}
}
}
assert(bul != 1e9);
curans += bul;
m |= minm;
//if(m==18){
// cerr << a << sp <<sp << sp << bul << endl;
//}
}
}
if(curans < ans)
ansmask = m;
ans = min(curans,ans);
}
//cerr << bitset<8>(ansmask) << endl;
assert(ans != 1e9);
cout << ans << endl;
}
Compilation message
kronican.cpp: In function 'int main()':
kronican.cpp:88:9: warning: variable 'ansmask' set but not used [-Wunused-but-set-variable]
88 | int ansmask = 0;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
24 ms |
492 KB |
Output isn't correct |
| 9 |
Incorrect |
23 ms |
364 KB |
Output isn't correct |
| 10 |
Incorrect |
119 ms |
1008 KB |
Output isn't correct |
