传送门
解题思路
很容易想到用最短路来解决这一道问题（题解法），因为两个点之间可以互相无限走，所以如果到某个点的最短路是x，那么x+2，x+4也一定能够达到。
但是如何保证这是正确的呢？比如说到某个点的最短路是x，为什么不可能走一下弯路，是某一条路径的长度是x+1或者x+3或者x+5呢？
所以就用到了奇偶最短路。所谓奇偶最短路，就是对于每一个点，记录下走偶数步的最短路（ou[i]）和走奇数步的最短路（ji[i]），转移式为：
ji[v]=min(ou[u]+1,ji[v]);
ou[v]=min(ji[u]+1,ou[v]);
注意一定要用u去更新v，即距离近的去更新远的。
AC代码
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int maxn=100005; 7 int n,m,Q; 8 int ji[maxn],ou[maxn],vis[maxn],p[maxn]; 9 queue<int> q; 10 struct edge{ 11 int v,next; 12 }e[2*maxn]; 13 int cnt; 14 void insert(int u,int v){ 15 e[++cnt].v=v; 16 e[cnt].next=p[u]; 17 p[u]=cnt; 18 } 19 int main(){ 20 memset(ji,0x3f,sizeof(ji)); 21 memset(ou,0x3f,sizeof(ou)); 22 memset(p,-1,sizeof(p)); 23 cin>>n>>m>>Q; 24 for(int i=1;i<=m;i++){ 25 int u,v; 26 scanf("%d%d",&u,&v); 27 insert(u,v); 28 insert(v,u); 29 } 30 ou[1]=0; 31 q.push(1); 32 while(!q.empty()){ 33 int u=q.front(); 34 q.pop(); 35 vis[u]=0; 36 for(int i=p[u];i!=-1;i=e[i].next){ 37 int v=e[i].v; 38 if(ji[v]>ou[u]+1){ 39 ji[v]=ou[u]+1; 40 if(vis[v]==0){ 41 q.push(v); 42 vis[v]=1; 43 } 44 } 45 if(ou[v]>ji[u]+1){ 46 ou[v]=ji[u]+1; 47 if(vis[v]==0){ 48 q.push(v); 49 vis[v]=1; 50 } 51 } 52 } 53 } 54 for(int i=1;i<=Q;i++){ 55 int a,l; 56 scanf("%d%d",&a,&l); 57 if(((l&1)&&ji[a]<=l)||((!(l&1))&&ou[a]<=l))printf("Yes\n"); 58 else printf("No\n"); 59 } 60 return 0; 61 }
//CSP2019普及组 t4