题解 P5663 【加工零件】

· · 题解

没人写分层图的题解？？

设 i 号节点的偶节点为 i ,奇节点为 i+n

偶节点含义: 从1到该节点距离(永远)为偶数的节点；

奇节点定义: 从1到该节点距离(永远)为奇数的节点；

由于 奇数+1=偶数，偶数+1=奇数

所以如果 u 和 v 之间有传输带，

那么只用把 (u,v+n),(u+n,v),(v+n,u),(v,u+n) 连边即可

然后以1为起点跑最短路

由题意可知：

当 L \equiv 1 (mod \ 2) 时，当 L \geq dis[a+n] 时输出Yes,否则输出No

同理，

当 L \equiv 0 (mod \ 2) 时，当 L \geq dis[a] 时输出Yes,否则输出No

注意,数组要开2倍

然后...就是---

code: (简单明了)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 200020
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
int head[N],cnt,n,m,Q,dis[N],vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
struct Edge{
    int to,nxt;
}edge[N<<1];
void add(int a,int b){
    cnt++;
    edge[cnt].to=b;
    edge[cnt].nxt=head[a];
    head[a]=cnt;
}
int main(){
    n=read(),m=read(),Q=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add(u,v+n),add(v+n,u),add(u+n,v),add(v,u+n);
    }
   //一下是最短路板子
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(make_pair(dis[v],v));
            }
        }
    }
   //开始判断
    while(Q--){
        int a=read(),L=read();
        if(L&1){
            printf(dis[a+n]<=L?"Yes\n":"No\n");
        }
        else{
            printf(dis[a]<=L?"Yes\n":"No\n");
        }
    }
    return 今年pj的难度怎么匀给tg啦?(大雾);
}

Froggy's blog

呱!!