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; } }