思路

首先暴力建图肯定不行的,直接被卡死。
那么想如何优化。
首先我们可以按位操作,把32位看成点,然后对每个点拆点。
即:对于第 位(二进制) 有两个点,(入点)和 (出点) , 连一个边,边权为
然后对于输入的 ,如果当前 在第 位(二进制)是 ,那么这个点向 连一条边权为 的边, 向该点连一条边权为 的边。
最后跑一遍最短路即可。
正确性:
题目要求的是如果 & ,那么这两个点之间可以连边,边权为 &
我们这么建图如何保证所走的边的边权是两个点的 & 呢。
首先假设存在一条最短路: 指向 的,以上建图方式,他们的边权一定是 & 吗?答案是肯定的,假设我们最短路已经搜到 这里了,从 开始去找其他的点,它要走到 ,那么它下一步的点一定是 点权二进制位数都有的,且是最低位(符合最短路贪心的思路)。

参考代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;
struct node{
    int v;
    ll w;
    bool operator < (const node &a)const{
        return w > a.w;
    }
};
vector<node>sp[man];
ll a[man];

void add(int u,int v,ll w){
    sp[u].push_back(node{v,w});
}
priority_queue<node>q;
ll dis[man];
bool vis[man];int n;
void dij(int s,int num){
    for(int i = 1;i <= num;++i)dis[i] = 1e18,vis[i] = 0;
    dis[s] = 0;
    q.push(node{1,0});
    while(q.size()){
        node tp = q.top();
        q.pop();
        if(vis[tp.v])continue;
        vis[tp.v] = 1;
        for(auto it:sp[tp.v]){
            int v = it.v;
            ll w = it.w;
            if(vis[v])continue;
            if(dis[v]>dis[tp.v] + it.w){
                dis[v] = dis[tp.v] + it.w;
                q.push(node{v,dis[v]});
            }
        }
    }
    if(dis[n]==1e18)printf("Impossible\n");
    else printf("%lld\n",dis[n]);
}


signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 1;i <= n;++i){
            scanf("%lld",&a[i]);
        }
        int num = n+1;
        for(int i = 0;i <= 32;++i)add(num+i,num+40+i,(1ll<<i));
        for(int i = 1;i <= n;++i){
            for(int j = 0;j <= 32;++j){
                if((a[i]>>j)&1){
                    add(i,num+j,0);
                    add(num+40+j,i,0);
                }
            }
        }
        dij(1,num+100);
        for(int i = 1;i <= num+100;++i){
        //    cout<<"u:"<<i<<endl;
        //    for(auto it:sp[i])cout<<it.v<<" ";
        //    cout<<endl;
            sp[i].clear();
        }
    }
    return 0;
}