无向图最小环

luckydrawbox · 2022-11-14 13:08:42 · 个人记录

变量

函数

代码

struct Min_Ring{
    ll val[N][N];
    ll min_ring(int n,ll **d){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                val[i][j]=d[i][j];
        ll ans=1e9;
        for(int k=1;k<=n;k++){
            for(int i=1;i<k;i++)
                for(int j=i+1;j<k;j++)
                    ans=min(ans,val[i][j]+d[i][k]+d[k][j]);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    val[j][i]=val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
        }
        return ans;
    }
};