题解：P5663 [CSP-J2019] 加工零件

阅读理解，脑袋尖尖QWQ

//由题，建分层图，跑最短路
//最短路得值判奇偶 
#include<bits/stdc++.h>
using namespace std;
//全局量 
const int M=1e6+110;
//链式前向星
struct w{
	int next,to;
}e[M];
int head[M],k=0;
void add(int u,int v){
	k++;
	e[k].next=head[u];
	e[k].to=v;
	head[u]=k;
}
//重点，分层
//奇数路径由偶数路径转移
//偶数路径由奇数路径转移
//spfa//离线操作，询问为O(1) 
int dis[M][2];
bool vis[M];
void spfa(){//标准spfa 
	queue<int>q;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[1][0]=0;
	vis[1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next){//注意转移→奇偶 
			int v=e[i].to;
			if(dis[u][0]+1<dis[v][1]){
				dis[v][1]=dis[u][0]+1;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
			if(dis[u][1]+1<dis[v][0]){
				dis[v][0]=dis[u][1]+1;
				if(!vis[v]){//不用担心重复入队 
					vis[v]=1;
					q.push(v);
				}
			}
		} 
	}
}
int main(){
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){//建图（双向） 
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	spfa();
	for(int i=1;i<=q;i++){
		int qq,jie;
		cin>>qq>>jie;
		
		//只要有3的路径，就一定有1的路径
		//但如果只有1的路径，一定没有3的路径 
		
		if(jie%2==0){//偶数路径 
			if(dis[qq][0]<=jie) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
		if(jie%2==1){//奇数路径 
			if(dis[qq][1]<=jie) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		} 
	}
	return 0;	
}