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

这道题我用了最短路。

这道题数据较大，也涉及到了奇偶性，我这里用了最短路进行了预处理。我们先拆点，再用奇偶性算出这个点是否能在 \(\le L\) 步到达一号点。

#include <bits/stdc++.h>
using namespace std;
const int N=201000;
int n,m,Q;
vector <int> e[N];
int dis[N],q[N];
int main(){scanf("%d%d%d",&n,&m,&Q);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);e[2*u-2].push_back(2*v-1);e[2*v-2].push_back(2*u-1);e[2*u-1].push_back(2*v-2);e[2*v-1].push_back(2*u-2);//连边}for(int i=0;i<2*n;i++)dis[i]=1<<30;int h=1,t=1;q[t]=0,dis[0]=0;while(h<=t){int u=q[h];h++;for(int j=0;j<(int)e[u].size();j++){int v=e[u][j];if(dis[v]>dis[u]+1){dis[v]=dis[u]+1;t++;q[t]=v;}}}for(int i=0;i<Q;i++){int a,l;scanf("%d%d",&a,&l);if(e[0].empty())printf("No\n");//判是否有孤立点else{int u=2*a-2+(l%2);if(l>=dis[u])printf("Yes\n");else printf("No\n");}}
}