P5663 题解

__vector__ · 2021-12-17 20:20:20 · 个人记录

ZGC AK IOI!

\color{green}\text{AC算法：} dfs

这道题可以发现，其实就是在求 1 到要生产零件的工人 a的最短路，这个最短路的意思就是经过多少轮之后轮到轩轩（1 号）提供零件。显然，如果最短路 \le l，那么肯定会让轩轩提供原材料。
但是这样随便画个图就hack掉了，最后分析这个图，可以发现要开两个数组，分别存最短路为奇数和最短路为偶数的。分开之后即可通过。

放上我几个月前的代码：

#define lmnjuruo "这题的难度对于lmn蒟蒻来说为IOI/IOI+"
#define zgcshenxian "这题的难度对于zgc神仙来说为入门-"
#include <iostream>//cin,cout
#include <cstring>//string类
#include <cstdio>//scanf,printf
#include <cstdlib>//freopen,system等
#include <string>//string类
#include <algorithm>//算法库
#include <cmath>//数学库
#include <iomanip>//输出控制
#include <vector>//容器系列
#include <set>//不常用
#include <map>//hash映射
#include <deque>//双向容器
#include <queue>//优先队列
#include <bitset>//二进制
#include <ctime>
#define PI 3.14//圆周率
#define inf 0x3f3f3f3f//无穷大
#define ll long long//不开long long见祖宗
#define ull unsigned long long
#define reg register//寄存器存放
#define O2 ios::sync_with_stdio(false)//加速cin
#define ZGC_AKIOI "100%"
#define LHX_AKIOI "100%"
#define DY_AKIOI "100%"
#define DCY_AKIOI "100%"
#define ZGC "邹神过河拆黑题，顺手AKIOI"
#define lmn "lmn蒟蒻过河被红题挡，顺手爆零模拟赛"
#define lmntrl "lmn蒟蒻爆零CSP-J2021"
using namespace std;
inline int read()//快读
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    char F[200];
    int tmp=x>0?x:-x ;
    if(x<0)putchar('-') ;
    int cnt=0 ;
       while(tmp>0)
       {
           F[cnt++]=tmp%10+'0';
           tmp/=10;
       }
       while(cnt>0)putchar(F[--cnt]) ;
}
const int maxn=1e5+5;
int n,m,q;
vector<int> edge[maxn];
int disou[maxn],disji[maxn];
void bfs()
{
    memset(disou,0x3f3f3f3f,sizeof(disou));
    memset(disji,0x3f3f3f3f,sizeof(disji));
    queue< pair<int,int> > que;
    for(int i=0;i<edge[1].size();i++)
    {
        int to=edge[1][i];
        disji[to]=1;
        que.push(make_pair(1,to));
    }
    while(!que.empty())
    {
        int u=que.front().second;
        int dis=que.front().first;
        que.pop();
        for(int i=0;i<edge[u].size();i++)
        {
            int to=edge[u][i];
            if(dis&1)//更新答案后当前为偶数 
            {
                if(disou[to]>dis+1)
                {
                    disou[to]=dis+1;
                    que.push(make_pair(dis+1,to));
                }
            }
            else
            {
                if(disji[to]>dis+1)
                {
                    disji[to]=dis+1;
                    que.push(make_pair(dis+1,to));
                }
            }
        }
    }
}
int main()
{
    O2;
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    bfs();
    for(int i=1;i<=q;i++)
    {
        int a,l;
        cin>>a>>l;
        if(l&1)
        {
            if(disji[a]<=l)puts("Yes");
            else puts("No");
        }else
        {
            if(disou[a]<=l)puts("Yes");
            else puts("No");
        }
    } 
    return 0;
}