D. Shortest Cycle

D. Shortest Cycle

A[i]&A[j]!=0连边，

求图中最小环

N>128 时必有3环

其他暴力跑

folyd最小环

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define sc(x) scanf("%I64d",&x);

#define read(A) for(int i=0;i<n;i++) scanf("%I64d",&A[i]);

ll A[];

ll B[][];

ll dis[][];

ll N;

#define inf 1e18

ll floyd()

{

    ll MinCost = inf;

    for(int k=; k<=N; k++)

    {

        for(int i=; i<k; i++)

            for(int j=i+; j<k; j++)

                MinCost = min(MinCost,dis[i][j]+B[i][k]+B[k][j]);

        for(int i=; i<=N; i++)

            for(int j=; j<=N; j++)

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

    }

    if(MinCost==inf)return -;

    else return MinCost;

}

int main()

{

    // ll N;

    sc(N);

    ll _k=;

    for(int i=; i<=N; i++)

    {

        sc(A[_k]);

        if(A[_k]!=)_k++;

    }

    if(_k>=)

    {

        puts("");

    }

    else

    {

        N=_k-;

        for(int i=; i<=N; i++)

        {

            for(int j=; j<=N; j++)

            {

                if(i!=j&&(A[i]&A[j]))

                {

                    B[i][j]=;

                    dis[i][j]=;

                }

                else if(i==j)

                {

                    B[i][j]=;

                    dis[i][j]=;

                }

                else

                {

                    B[i][j]=inf;

                    dis[i][j]=inf;

                }

            }

        }

        cout<<floyd()<<'\n';

    }

}