AI 生成摘要
本题考验图论思维，核心是将零件生产转化为图中两点间路径长度问题。若 A 生产第 L 阶段零件需经过 B 生产 L-1 阶段，则实质取决于 A、B 间是否存在长度为 L 的路径。由于可行路径长度具有奇偶性规律（存在长度 X 的路径必存在长度 X+2n 的路径），只需分别记录从起点到各点的奇数和偶数最短路径，通过 BFS 求解后，若最短路径小于等于 L 且奇偶性匹配，则输出 Yes。

这题有点思维含量，但是还行。 然而考试时脑抽没想到.png

题意比较清楚，所以我们直接看做法

解题思路

部分分思路

很容易想到 dfs 电风扇 暴力求解 ，于是光荣地 T 飞了。代码就不放了，大家都会写。

当然，也有一些优化措施。

一般，考场上写暴力的话能写出 40pts 的代码，只有前 8 个点。

经过一些记忆化处理，可以骗到 60pts。

再经过一些对 memset 毒瘤处理，可以再骗走 20pts。

具体方法可以看这篇题解。

AC 思路

考虑最短路

根据题意我们可以设原材料为 $0$ 阶段的零件

先看这张图：

我们可以发现如果 $A$ 想生产 $L$ 阶段 $(L≥2)$ 的零件，就需要 $B$ 生产 $L-1$ 阶段的零件,就需要 $A$ 生产 $L-2$ 阶段的零件。

所以问题的实质就是看 $A$ 和 $B$ 之间有没有长度为 $L$ 的路径。

仔细思考，我们可以发现：如果 $A$ 到 $B$ 有长度为 $X$ 的路径，则 $A$ 到 $B$ 一定有长度为 $(X + n * 2)$ 的路径，但不一定有长度为 $(X + n * 2 - 1)$ 的路径。$(n \ge 1)$

所以，我们要对每个点求一遍奇数路径，和偶数路径。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, q, ji[N], ou[N];
bool vis[N];
vector<int> e[N];
void bfs()
{
    memset(ji, 0x3f, sizeof(ji));
    memset(ou, 0x3f, sizeof(ou));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    ou[1] = 0;
    vis[1] = 1;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto v : e[u])
        {
            if (ou[u] + 1 < ji[v])
            {
                ji[v] = ou[u] + 1;
                if (!vis[v])
                    q.push(v), vis[v] = 1;
            }
            if (ji[u] + 1 < ou[v])
            {
                ou[v] = ji[u] + 1;
                if (!vis[v])
                    q.push(v), vis[v] = 1;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    bfs();
    while (q--)
    {
        int a, l;
        cin >> a >> l;
        if (l % 2 == 0)
        {
            if (ou[a] > l)
                puts("No");
            else
                puts("Yes");
        }
        else
        {
            if (ji[a] > l)
                puts("No");
            else
                puts("Yes");
        }
    }
}