D. Shortest Cycle
不要用memset进行二维数组的初始化,会出现严重的错误!!!!!!!!!!!!!!!!!!!!!!!!!
话说,不要用memset进行初始化了8
收获:floyd求解最小环!!!!
get!
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define mem(a,n,val) for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)a[i][j]=val;
typedef long long ll;
const int max_n = 1e5+100;
const int inf = 100000;
ll a[max_n];
int n;
int val[210][210];
int dis[210][210];
inline int floyd() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) dis[i][j] = val[i][j];
int ans = inf;
for (int k = 1; k <= n; ++k) {
for (int i = 1; i < k; ++i)
for (int j = 1; j < i; ++j)
ans = min(ans, dis[i][j] + val[i][k] + val[k][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin>>n;int nn = 0;
for (int i=1;i<=n;++i){
ll num;cin>>num;
if (num!=0)a[++nn]=num;
}n=nn;
if (n>=210){
cout<<"3\n";
}
else{
for (int i=0;i<=n;++i){
for (int j=0;j<=n;++j){
cout<<val[i][j]<<" ";
}puts("");
}
for (int i=1;i<=n;++i){
for (int j=i+1;j<=n;++j){
if (a[i]&a[j]){
val[i][j]=1;
val[j][i]=1;
}
}
}
int ans = floyd();
if (ans==inf)cout<<"-1\n";
else cout<<ans<<endl;
}
}