| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 373060 | 2021-03-03T08:32:32 Z | maozkurt | Kronican (COCI16_kronican) | C++17 | 0 ms | 0 KB |
#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;
}