思路
首先暴力建图肯定不行的,直接被卡死。
那么想如何优化。
首先我们可以按位操作,把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; }