T3-6 [CSP-J 2019] 加工

关键观察：奇偶分层 BFS

图是无权图（每条边步数为 1），所以用 BFS 求最短路。

但这里不是"最短路 $\leq L$"就行，而是要求恰好走 $L$ 步。因为可以沿一条边来回走（浪费 2 步），所以：

如果从 $a$ 到 1 的最短路是 $d$，且 $d$ 和 $L$ 奇偶性相同，且 $d \leq L$，则答案为 Yes。

原因：最短路走 $d$ 步到达后，剩余 $L - d$ 步是偶数，可以在任意一条边上来回走消耗掉。

但图中可能存在奇数环！如果存在经过节点 1 的奇数环，那么奇偶性可以切换。所以需要分别记录：

• $dis_{even}[v]$：从节点 1 出发，走偶数步到达 $v$ 的最短步数
• $dis_{odd}[v]$：从节点 1 出发，走奇数步到达 $v$ 的最短步数

对于查询 $(a, L)$：

• 如果 $L$ 是偶数：检查 $dis_{even}[a] \leq L$
• 如果 $L$ 是奇数：检查 $dis_{odd}[a] \leq L$

---

实现方法：奇偶分层 BFS

把每个节点拆成两个状态 $(v, 0)$ 和 $(v, 1)$，分别表示走偶数步和奇数步到达 $v$。

从 $(1, 0)$ 开始 BFS（走 0 步到达节点 1，0 是偶数）。

每走一条边，奇偶性翻转：$(u, p) \to (v, p \oplus 1)$。

---

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int INF = 0x3f3f3f3f;

vector<int> g[N];           // 邻接表存无向图
int dis[N][2];              // dis[v][0] = 偶数步到达 v 的最短步数
                            // dis[v][1] = 奇数步到达 v 的最短步数

int main() {


    int n, m, q;
    cin >> n >> m >> q;

    // 读入无向图
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);          // u → v
        g[v].push_back(u);          // v → u（双向）
    }

    // 初始化距离为无穷大
    memset(dis, 0x3f, sizeof dis);

    // BFS，起点是 (节点1, 偶数步)，距离为 0
    dis[1][0] = 0;                   // 走 0 步（偶数）到达节点 1

    // 队列中存 (节点编号, 奇偶性)
    queue<pair<int, int>> q_bfs;
    q_bfs.push({1, 0});

    while (!q_bfs.empty()) {
        auto [u, p] = q_bfs.front(); q_bfs.pop();

        for (int v : g[u]) {                    // 遍历 u 的邻居 v
            int np = p ^ 1;                     // 走一步后奇偶性翻转
            if (dis[v][np] > dis[u][p] + 1) {   // 如果能更新最短距离
                dis[v][np] = dis[u][p] + 1;      // 更新
                q_bfs.push({v, np});              // 入队
            }
        }
    }

    // 处理查询
    while (q--) {
        int a, L;
        cin >> a >> L;

        // L 的奇偶性决定看 dis[a][0] 还是 dis[a][1]
        int parity = L % 2;                // L 是奇数则 parity=1，偶数则 parity=0

        if (dis[a][parity] <= L)            // 最短步数 <= L 且奇偶相同，可以到达
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}