「NOIP十连赛day1」散步walk - 拆点最短路

题目大意

略

---

初步想法

首先这道题肯定不能暴力建边。
题目中与运算这个条件非常的特殊，如果不暴力建边，就要考虑如何添加辅助点/边，使得和原题等价。

考虑到权值最大为$2^{20}=1048576$，那么可以将权值加入复杂度的考虑内。
因为子集关系的权值为1，那么我们将权值建成$2^{20}$个点，一个权值到子集的权值连一条边权为0的边，每个点到它的权值连一条边权为1的边，权值到点连一条边权为0的边，这样就和题意等价了。
因为点边太多，使用dijkstra要超时。考虑到边权只可能为0或1，因此我们可以采用Bfs的方法，只要先扩展边权为0的结点，再扩展边权为1的结点就可以保证无误。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=1248580;
int n,m,Dist[maxn],cnt=1<<20;
queue<int>Q;
vector<int>edges[maxn],edges0[maxn];
void AddEdge1(int x,int y) {
	edges[x].push_back(y);
}
void AddEdge2(int x,int y) {
	edges0[x].push_back(y);
}
void Dfs(int Now,int dist) { //扩展边权为0的边 
	if(Dist[Now]>=0)return;
	Q.push(Now);
	Dist[Now]=dist;
	for(int i=0; i<edges0[Now].size(); i++) {
		int Next=edges0[Now][i];
		Dfs(Next,dist);
	}
	if(Now>=cnt)return;
	for(int i=0; i<20; i++)
		if(Now&(1<<i))Dfs(Now^(1<<i),dist);
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++) {
		int x=Get_Int();
		AddEdge1(cnt+i,x);
		AddEdge2(x,cnt+i);
	}
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge1(cnt+x,cnt+y);
	}
	for(int i=0; i<=cnt+n; i++)Dist[i]=-1;
	Dfs(cnt+1,0);
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		for(int i=0; i<edges[Now].size(); i++) {
			int Next=edges[Now][i];
			Dfs(Next,Dist[Now]+1);
		}
	}
	for(int i=1; i<=n; i++)printf("%d\n",Dist[cnt+i]);
	return 0;
}