原题链接

题解

请仔细读题！！！

如果1号工人需要提供原材料，那么代表 \(a_i \to 1\) 存在一条长度为 \(L_i\) 的路径（可以重复走）

由于重复走不会改变路径长度的奇偶性，所以一定存在一条奇偶性相同，且长度小于 \(L_i\) 的路径，所以只要求从点1出发到各个点奇偶最短路即可

code

#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];

struct fresh
{
    int pos,val;
    bool operator<(const fresh &b) const{return b.val<val;}
};

int dis[100005][2];

int main()
{
    memset(dis,0x3f,sizeof dis);
    int n,m,Q;
    cin>>n>>m>>Q;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    priority_queue<fresh> q;
    q.push({1,0});

    while(q.size())
    {
        int now=q.top().pos,val=q.top().val,id=(val&1);
        q.pop();
        if(dis[now][id]<=val) continue;
        dis[now][id]=val;
        for(auto next:G[now])
        {
            if(dis[next][1-id]>val+1)
            {
                q.push({next,val+1});
            }
        }
    }

    while(Q--)
    {
        int a,l;
        cin>>a>>l;

        if(dis[a][l&1]<=l) puts("Yes");
        else puts("No");
    }
    return 0;
}