zcmimi's blog
avatar
zc
2020-05-04 01:28:00
  • 本文总阅读量
查看原题

点击跳转

容易发现,只要这个点与1之间存在某条路径长度(\le阶段数)+阶段数为偶数的,那1就得提供原材料

我们分别求出长度为奇数、偶数的最短路长度即可判断

#include<bits/stdc++.h>
#define gc getchar()
void in(int &x){x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);if(f)x=-x;}
const int N=100011;
int n,cnt,head[N],q[N<<1],d[2][N];
bool p[N<<1];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
void bfs(){
    int h=0,t=1,x;bool v;
    q[0]=1,p[0]=0,d[0][1]=2;
    while(h<t){
        x=q[h],v=p[h++];
        for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
            if(!d[!v][to])
                d[!v][to]=d[v][x]+1,
                q[t]=to,p[t++]=!v;
    }
}
int main(){
    int m,q,x,y;
    in(n),in(m),in(q);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    bfs();
    while(q--)
        in(x),in(y),
        puts((!d[y&1][x]||d[y&1][x]>y+2)?"No":"Yes");
}
LG 5663 加工零件
comment评论
Search
search