题目
题目来源于北华大学计算机程序设计算法提高训练营个人赛的J题，邀请码:bhu2022。
给出一个n(1\leq n\leq 10^6)点m边的无向图每条边长为1，每个点拥有一个0/1的点权，0表示雌性，1表示雄性。一共有q次询问，每次询问x，回答距离点x最近的异性的最短距离是。
思路
考虑到数据范围比较大，肯定不能用暴力，所以需要用两遍bfs，一次从所有的0出发，去更新每个1点到0的最短距离；一次从所有的1出发，去更新每个0点到1的最短距离。
令f[i][0/1]，其中f[i][0]表示点i到0的最短距离，f[i][1]表示点i到1的最短距离。
举个例子：
我一开始选取所有的1进入队列，每次只传递到相邻的且异性的地方，并且没有走过（因为是bfs，所以一旦走过那么一定不能更新最短距离），然后让其加入队列，并且距离+1。
inline void bfs(int sex)
{
queue<int> q;
for (int i=1;i<=n;i++)
{
if (a[i]==sex)
q.push(i),f[i][sex] = 0;//自己到自己性别距离当然为0
}
while (!q.empty())
{
int x = q.front();q.pop();
for (int i=head[x];i;i=edge[i].next)
{
int y = edge[i].to;
if (f[y][sex]==-1 && a[y]!=sex)
{
f[y][sex] = f[x][sex]+1;//等于上一次+1
q.push(y);
}
}
}
}所以这个图我加入一开始是bfs(1)，也就是让3进入队列，更新f[3][1] = 0让其传递，当传到2的时候更新f[2][1] = f[3][1] + 1 = 1，这个意义也就是点2到1的最短距离为1，那么接下来是否会传递到1呢？会！因为1与3异性，也同样更新了f[1][1] = f[2][1] + 1 = 2
这样下来，我bfs(1)之后让所有的0都获得了到1的最短距离，同理，我再来一遍bfs(0)即可。最后读入O(1)输出答案即可。
代码
int f[N][2];
inline void bfs(int sex)
{
queue<int> q;
for (int i=1;i<=n;i++)
{
if (a[i]==sex)
q.push(i),f[i][sex] = 0;
}
while (!q.empty())
{
int x = q.front();q.pop();
for (int i=head[x];i;i=edge[i].next)
{
int y = edge[i].to;
if (f[y][sex]==-1 && a[y]!=sex)
{
f[y][sex] = f[x][sex]+1;
q.push(y);
}
}
}
}
inline void Case_Test()
{
cin>>n>>m>>q;
for (int i=1;i<=n;i++)
{
f[i][0] = f[i][1] = -1;
cin>>a[i];
}
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
add(u,v);add(v,u);
}
bfs(0);
bfs(1);
while (q--)
{
cin>>x;
cout<<f[x][!a[x]]<<endl;
}
}