codeforces #580(div.2) Shortest Cycle（floyd最小环）

原题连接：http://codeforces.com/contest/1206/problem/D

参考博客：https://blog.csdn.net/weixin_43847416/article/details/99964140

根本没看懂题，看了这位大佬博客后，豁然开朗。题目给的每个权值 a[i] 的范围最大是1e18，二进制下最多64位。
如果64位中有某一位的1的出现数大于 2 了，那么很明显，最小环就是3（该位循环）。
换个说法，在最坏的情况下，给出了 n 个数，其中有超过 128 个不为 0的数，那么答案一定是3（因为当有128个不为0的数时，64位每一位的个数都是2，只要再随便来个不为0的数，都会出现大于2的位数，构成 3 的环）

所以我们只要考虑不为 0 的数的个数小于等于128的情况就行了，这个时候 n 就很小了，我是用的floyd求最小环

关于floyd求最小环，可以看一下这位大佬的博客：https://www.cnblogs.com/DF-yimeng/p/8858184.html

代码：

#include <bits/stdc++.h>
using namespace std;
long long a[100010];
long long e[200][200];
long long c[200][200];
long long inf=999999999;
long long minf=99999999999999999;
int main()
{
    long long n;
    long long op=0,r;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {scanf("%lld",&r);
    if(r!=0)
    {a[op]=r;
    op++;}}
    if(op>128)
    {cout<<"3"<<endl;}
    else
    {
        n=op;
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(a[i]&a[j])
                {e[i][j]=e[j][i]=1;
                c[i][j]=c[j][i]=1;}
                else
                {e[i][j]=e[j][i]=999999999;
                c[i][j]=c[j][i]=inf;}
            }
        }
        long long ans=minf;
        for(int k=0;k<n;k++)
        {
            for(int i=0;i<k;i++)
            {
                for(int j=i+1;j<k;j++)
                {
                    long long tmp=e[i][k]+e[k][j]+c[i][j];
                    if(tmp<ans)
                    {ans=tmp;}
                }
            }
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(c[i][k]+c[k][j]<c[i][j])
                    {c[i][j]=c[i][k]+c[k][j];}
                }
            }
        }
        if(ans==minf||ans>inf)
        {printf("-1\n");}
        else
        {printf("%lld\n",ans);}
    }
    return 0;
}