牛妹游历城市

最近，牛妹天天宅在家里，真是憋死人了。他决定出去旅游。

牛妹现在正在1号点（自己家里），他决定前往n号点（牛妹想去的地方），中途可以多次经过1~n号点。

现在，已知每个点都有个权值 $a_i$ ，如果 $a_i \& a_j ≠0$ ，则i号点和j号点之间连有一条双向边，权值为 $lowbit(a_i \& a_j)$ 。

他想要最小化自己的行走距离，但是他计算不出来qaq。相信全牛客最聪明的你一定会吧！

Tips:

$\&$ 是位运算中and的意思，lowbit(n)的值是最大的 $2^x$ ，满足 $2^x | n$ 。

例如 $lowbit(5)=lowbit((101)_2)=1,\ lowbit(8)=lowbit((1000)_2)=8$ 。

#include<bits/stdc++.h> using namespace std; int main() { int i,j,n,T; long long x,one=1,t,Min[35]; scanf("%d",&T); while(T--) { scanf("%d",&n); t=0,memset(Min,0x3f,sizeof(Min)); for(i=0;i<n;i++) { scanf("%lld",&x); if(i)t=1e18; for(j=0;j<32;j++)if((one<<j)&x)t=min(t,Min[j]+(one<<j)); for(j=0;j<32;j++)if((one<<j)&x)Min[j]=min(Min[j],t); } if(t==1e18)printf("Impossible\n"); else printf("%lld\n",t); } return 0; }

详情