1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
|
#include <cassert> #include <iostream> #include <vector> #include <queue> using namespace std; const int N = 1005; const long long inf=0x3f3f3f3f; long long arr[N*100]; long long gra[N][N]; long long m[N][N]; long long b[N*100]; long long n,res; void () { res=inf; for(int k=1;k<=n;k++){ for(int i=1;i<k;i++){ for(int j=1;j<k;j++) { if(i==j) continue; res=min(res,gra[i][j]+m[i][k]+m[k][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) continue; gra[i][j]=min(gra[i][j],gra[i][k]+gra[k][j]); } } } } int main() { scanf("%lld", &n); int cnt=1; for (int i = 1; i <= n;i++) { scanf("%lld", &arr[i]); if(arr[i]) b[cnt++]=arr[i]; } if(cnt>200){ printf("3n"); return 0; } for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { if(i==j) continue; m[i][j]=gra[i][j]=inf; } } for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { if(i==j) continue ; if((b[i]&b[j])!=0) gra[i][j]=1; m[i][j]=gra[i][j]; } } n=cnt; floy(); if(res==inf) printf("-1n"); else printf("%lldn",res); }
|
近期评论