Jennie

我们充分意识到数据范围小的可怕，避免出现奇环只要二分图随机染色然后走黑白边就可以了。

然后怎么染色？随机啊，只要运气够好就不是事。

6000次足够了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n;
int kk;
int ans=9999999999999;
int ma[100][100];
int f[100][100];
int col[200];
int dis[100][100];
signed main(){
    read(n);read(kk);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            read(dis[i][j]);
        }
    }
    int t=5000;
    srand(20050419);
    while(t--){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=kk;++j){
                f[i][j]=999999999999999;
            }
            f[i][0]=999999999999999;
        }
        f[1][0]=0;
        for(int i=1;i<=n;++i){
            col[i]=rand()&1;
        }
        for(int k=1;k<=kk;++k){
            for(int j=1;j<=n;++j){
                for(int i=1;i<=n;++i){
                    if(col[i]^col[j]){
                        f[i][k]=min(f[i][k],f[j][k-1]+dis[j][i]);
                    }
                }
            }
        }
        ans=min(ans,f[1][kk]);
    }
    cout<<ans;
    return 0;
}