在比特镇一共有 n 个街区,编号依次为 1 到 n,它们之间通过若干条单向道路连接。
比特镇的交通系统极具特色,除了 m 条单向道路之外,每个街区还有一个编码 vali,不同街区可能拥有相同的编码。如果 vali and valj = valj,即 vali 在二进制下与 valj 做与运算等于 valj,那么也会
存在一条额外的从 i 出发到 j 的单向道路。
Byteasar 现在位于 1 号街区,他想知道通过这些道路到达每一个街区最少需要多少时间。因为比特镇的交通十分发达,你可以认为通过每条道路都只需要 1 单位时间。
解法
val规则不能直接连边,不能枚举判断
所以要将它转化
我们新建2^20个点,将这些点与val值为其的点相连
由于我用的是spfa和优先队列,所以需要虚点到实点的距离为1,实点到虚点的距离为0,虚点与虚点之间的距离为0
如果这个反一下,同一个实点到达的实点和虚点距离就是一样的,而虚点之间转移无代价,就会导致答案大了1
至于虚点之间的转移,每次将其位数上的一个1删去,如此转移即可
ac代码
#include<bits/stdc++.h>
#define N 200010
#define M 300010
#define lim (1<<20)
#define v e[i].to
using namespace std;
int n,m,a,b,cnt,dis[N+lim],head[N+lim];
struct node{int to,w,next;}e[2*N+M];
struct Node{int id;bool operator<(const Node b)const{return dis[id]>dis[b.id];}}u;
priority_queue<Node>q;
void add(int x,int y,int z){e[++cnt]={y,z,head[x]},head[x]=cnt;}
void spfa()
{
while(!q.empty())
{
u=q.top(),q.pop();
if(u.id<=lim)for(int i=0;i<20;i++)
if(u.id>>i&1)if(dis[u.id^(1<<i)]==-1)
dis[u.id^(1<<i)]=dis[u.id],q.push({u.id^(1<<i)});
for(int i=head[u.id];i!=-1;i=e[i].next)
if(dis[v]==-1)dis[v]=dis[u.id]+e[i].w,q.push({v});
}
}
int main()
{
freopen("walk.in","r",stdin),freopen("walk.out","w",stdout);
memset(head,-1,sizeof(head)),memset(dis,-1,sizeof(dis)),scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a),add(lim+i,a,0),add(a,lim+i,1);
for(int i=1;i<=m;i++)scanf("%d%d",&a,&b),add(lim+a,lim+b,1);
q.push({lim+1}),dis[lim+1]=0,spfa();
for(int i=1;i<=n;i++)printf("%d\n",dis[i+lim]);
}