图论一般技巧新建虚点。
新建2^k个虚点。
四种转移。普通点n，新点k。
n->n 1
n->k(自己的) 0
k->k 0
k->n 1
本题bfs,边权为1，则最先扫到最优，要避免重复扫。
使虚点只用来更新一次，只入队一次，从而避免重复考虑。
枚举子集：见小技巧标签的博客。
对于每个点枚举子集，(2^k)^2;
但是要是每个点只扫一次。
发现子集如果扫过，子集的子集一定扫过。
所以每次只考虑下一层子集，放到队列里即可。
O(n+m+2^k)
#include<bits/stdc++.h> #define F(i,a,b) for(rg int i=a;i<=b;++i) #define LL long long #define rg register #define il inline #define pf(a) printf("%d ",a) #define phn puts("") using namespace std; int read(); /* 单向双向 */ #define N 300010 #define M 1000010 #define ID 2000010 int n,m,K,val[N],ok[ID]; int to[M],fir[M],head[ID],cnt; il void add(int x,int y){to[++cnt]=y;fir[cnt]=head[x];head[x]=cnt;} int dis[ID],vis[ID],id[1500010],gx[ID]; deque<int>q; il int max(int x,int y){return x>y?x:y;} #define inp(x) q.push_front(x) #define inb(x) q.push_back(x) #define out() q.pop_front() int main(){ n=read();m=read(); F(i,1,n)val[i]=read(),K=max(K,val[i]),ok[val[i]]=1; F(i,0,K)id[i]=n+i+1; F(i,1,n){ add(id[val[i]],i); } rg int u,v,x; F(i,1,m){ u=read();v=read();add(u,v); } memset(dis,-1,sizeof(dis)); inb(1);vis[1]=1;dis[1]=0; while(!q.empty()){ u=q.front();out(); // pf(u); if(u<=n){ for(rg int i=head[u];i;i=fir[i]){ if(!vis[v=to[i]]){ vis[v]=1;dis[v]=dis[u]+1;inb(v); } } if(!vis[id[x=val[u]]]){ vis[id[x]]=1;dis[id[x]]=dis[u]; } if(!gx[x]){ gx[x]=1; for(rg int i=head[id[x]];i;i=fir[i]){ if(!vis[v=to[i]]){ vis[v]=1;dis[v]=dis[u]+1;inb(v); } } for(rg int j=x;j;j-=j&-j){ if(!vis[v=id[x-(j&-j)]]){ vis[v]=1;dis[v]=dis[u];inp(v); } } } } else{ x=u-n-1; if(!gx[x]){ gx[x]=1; for(rg int i=head[u];i;i=fir[i]){ if(!vis[v=to[i]]){ vis[v]=1;dis[v]=dis[u]+1;inb(v); } } for(rg int j=x;j;j-=j&-j){ if(!vis[v=id[x-(j&-j)]]){ vis[v]=1;dis[v]=dis[u];inp(v); } } } } } F(i,1,n)printf("%d ",dis[i]); } il int read(){ int s=0;char ch; while(ch=getchar(),!isdigit(ch)); for(;isdigit(ch);s=s*10+(ch^48),ch=getchar()); return s; } /* g++ 1.cpp -g ./a.out 5 2 5 4 2 3 7 1 4 2 3 */
技巧总结：
树、图：边化点，点化边，互化。
图：建立虚点、拆点、源点汇点。
图到树：最小生成树。
树链：1、树剖 2、倍增 (最终询问可倍增下放)