Shortest Cycle

D. Shortest Cycle

You are given n integer numbers a1,a2,…,an. Consider graph on n nodes, in which nodes i, j (i≠j) are connected if and only if, ai AND aj≠0, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn’t have cycles at all.

Input
The first line contains one integer n (1≤n≤105) — number of numbers.

The second line contains n integer numbers a1,a2,…,an (0≤ai≤1018).

Output
If the graph doesn’t have any cycles, output −1. Else output the length of the shortest cycle.

Examples
inputCopy
4
3 6 28 9
outputCopy
4
inputCopy
5
5 12 9 16 48
outputCopy
3
inputCopy
4
1 2 4 8
outputCopy
-1
Note
In the first example, the shortest cycle is (9,3,6,28).

In the second example, the shortest cycle is (5,12,9).

The graph has no cycles in the third example.

这道题看似数据很大，实则暴力即可。

为什么呢？我们考虑没有答案为3的环时，是什么情况（只要二进制当中，同一位有3个1以上，那么答案肯定为3）。我们考虑二进制的每一位（一共64位），因为没有答案为3的环，那么根据贪心，我们肯定是考虑二进制只有一个1的情况，我们让1互相错开，但是又只有64位，所以当不为0的数字，超过 64 * 3 的时候，肯定答案为3。当不为0的数字，小于64 * 3的时候，暴力求最小环即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=1e3+10;
const int inf=0x3f3f3f3f;
int n,a[N*100],k;
int m,b[N*100];
int mp[N][N],g[N][N],res=inf;
void floyd()
{
	res=inf;
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<k;i++)
			for(int j=i+1;j<k;j++)
				res=min(res,g[i][j]+mp[i][k]+mp[k][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];	if(a[i]!=0)	k++,b[++m]=a[i];
	}	
	if(k>=200)	return printf("3"),0;
	for(int i=1;i<=m;i++)	for(int j=1;j<=m;j++)	if(i!=j)	mp[i][j]=g[i][j]=inf;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j)	continue;
			if((b[i]&b[j])!=0)	g[i][j]=1;
			mp[i][j]=g[i][j];	
		}	
	}
	n=m;
	floyd();
	if(res==inf)	cout<<-1<<endl;
	else	cout<<res<<endl;
	return 0;
}