2019 加工零件 · 方案二奇偶最短路

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1497 字

状态加一维奇偶，一次 BFS 回答所有工单

2019
图论

正文

// CSP-J 2019 复赛 T4 · 加工零件（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2019D
//
// 方案二 · 奇偶最短路 BFS
// 换一种问法：1 号要提供原材料，等价于
// 「从 a 出发，存在一条长度恰好为 L 的走法（点和边都允许重复走）到达 1 号」。
// 而只要存在一条长度为 d 的走法，且 d 与 L 奇偶相同、d <= L，
// 就可以在任意一条边上「走过去再走回来」补 2 步，一路凑到 L 步。
// 所以只要求出 1 号到每个点的「最短奇数步数」和「最短偶数步数」就够了。
// 做法：状态写成 (点, 当前步长的奇偶)，每走一条边奇偶翻转，跑一次 BFS。
// 复杂度：时间 O(n + m + q)，空间 O(n)。

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

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

vector<int> g[MAXN];
int dis[MAXN][2];   // dis[v][0]：1 号到 v 的最短偶数步；dis[v][1]：最短奇数步

int main() {
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);

    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);
        g[v].push_back(u);
    }

    memset(dis, 0x3f, sizeof(dis));
    queue<pair<int, int>> que;
    dis[1][0] = 0;
    que.push(make_pair(1, 0));

    while (!que.empty()) {
        int v = que.front().first;
        int p = que.front().second;
        que.pop();
        for (int w : g[v]) {
            int np = p ^ 1;                    // 走一条边，步长奇偶翻转
            if (dis[w][np] != INF) continue;
            dis[w][np] = dis[v][p] + 1;
            que.push(make_pair(w, np));
        }
    }

    while (q--) {
        int a, L;
        cin >> a >> L;
        int best = dis[a][L % 2];              // 只关心与 L 同奇偶的那一条
        if (best <= L) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

2019 加工零件 · 方案二 奇偶最短路

正文

CSP-J 标程 · 复赛真题的其它内容

2019 加工零件 · 方案二奇偶最短路