#include<bits/stdc++.h>
#define int long long
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
const int MAXN=3e5+10;
const int MAXP=1e2+10;
const ll inf=0X3f3f3f3f3f3f3f3f;
const int infi=INT_MAX;
const ll MOD=1e9+7;
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
int n,k,m[25][25],dp[(1<<21)][25];
bool z[(1<<21)][25];
int bt(int mask,int q){
if(z[mask][q]) return dp[mask][q];
if(q==k) return 0;
int b=inf;
fall(i,0,n-1){
if(!(mask & (1<<i))) continue;
fall(j,0,n-1)
if(i!=j && (mask & (1<<j))) b=min(b,bt(mask^(1<<i),q-1)+m[i][j]);
}
return dp[mask][q]=b;
}
int32_t main(){
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("multimoo.in","r",stdin);
//freopen("multimoo.out","w",stdout);
cin>>n>>k;
fall(i,0,n-1)
fall(j,0,n-1)
cin>>m[i][j];
cout<<bt((1<<n)-1,n)<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |