【题目来源】
AcWing：1164. 加工零件 - AcWing题库
【题目描述】
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 \(n\) 位工人，工人们从 \(1∼n\) 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 \(x\) 号工人想生产一个被加工到第 \(L(L>1)\) 阶段的零件，则所有与 \(x\) 号工人有传送带直接相连的工人，都需要生产一个被加工到第 \(L−1\) 阶段的零件（但 \(x\) 号工人自己无需生产第 \(L−1\) 阶段的零件）。
如果 \(x\) 号工人想生产一个被加工到第 \(1\) 阶段的零件，则所有与 \(x\) 号工人有传送带直接相连的工人，都需要为 \(x\) 号工人提供一个原材料。
轩轩是 \(1\) 号工人。现在给出 \(q\) 张工单，第 \(i\) 张工单表示编号为 \(a_i\) 的工人想生产一个第 \(L_i\) 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
【输入】
第一行三个正整数 \(n\)，\(m\) 和 \(q\)，分别表示工人的数目、传送带的数目和工单的数目。
接下来 \(m\) 行，每行两个正整数 \(u\) 和 \(v\)，表示编号为 \(u\) 和 \(v\) 的工人之间存在一条零件传输带。保证 \(u\neq v\)。
接下来 \(q\) 行，每行两个正整数 \(a\) 和 \(L\)，表示编号为 \(a\) 的工人想生产一个第 \(L\) 阶段的零件。
【输出】
共 \(q\) 行，每行一个字符串 Yes 或者 No。如果按照第 \(i\) 张工单生产，需要编号为 \(1\) 的轩轩提供原材料，则在第 \(i\) 行输出 Yes；否则在第 \(i\) 行输出 No。注意输出不含引号。
【输入样例】
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2
【输出样例】
No
Yes
No
Yes
No
Yes
【解题思路】
【算法标签】
《AcWing 1164 加工零件》 #最短路# #BFS# #拆点#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII; // 定义 pair 类型，存储节点编号和类型
const int N = 1e5 + 10, M = N * 2, INF = 1e9 + 1000; // 定义常量
vector<int> h[N]; // 邻接表存储图
queue<PII> que; // BFS 使用的队列，存储节点编号和类型
int n, m, q; // n 是节点数量，m 是边的数量，q 是查询数量
int dist[N][2]; // dist[i][0] 表示从节点 1 到节点 i 的偶数步数距离，dist[i][1] 表示奇数步数距离// BFS 函数，计算从节点 1 到其他节点的偶数步数和奇数步数距离
void bfs() {// 初始化距离数组为 INFmemset(dist, 0x3f, sizeof(dist));dist[1][0] = 0; // 起点到自身的偶数步数距离为 0que.push({1, 0}); // 将起点加入队列，类型为 0（偶数步数）while (!que.empty()) { // 当队列不为空时PII nd = que.front(); // 取出队首节点que.pop(); // 弹出队首节点// 遍历当前节点的所有邻接节点for (int i = 0; i < h[nd.first].size(); i++) {int j = h[nd.first][i]; // 邻接节点 jint type = nd.second ^ 1; // 切换类型（偶数步数 -> 奇数步数，奇数步数 -> 偶数步数）// 如果当前路径可以更新节点 j 的距离if (dist[j][type] > dist[nd.first][nd.second] + 1) {dist[j][type] = dist[nd.first][nd.second] + 1; // 更新距离que.push({j, type}); // 将节点 j 加入队列}}}
}int main() {cin >> n >> m >> q; // 读取节点数量 n、边的数量 m 和查询数量 q// 读取边的信息并构建图while (m--) {int a, b;cin >> a >> b; // 读取边的两个端点h[a].push_back(b); // 添加边 a -> bh[b].push_back(a); // 添加边 b -> a}bfs(); // 调用 BFS 函数计算距离// 处理查询while (q--) {int a, L;cin >> a >> L; // 读取查询的节点 a 和步数 L// 判断是否满足条件if (a == 1 && h[1].size() == 0) // 如果查询的是起点且起点没有邻接节点puts("No");else if (L >= dist[a][L & 1]) // 如果步数 L 大于等于节点 a 的对应类型距离puts("Yes");else // 否则puts("No");}return 0;
}
【运行结果】
3 2 6
1 2
2 3
1 1
No
2 1
Yes
3 1
No
1 2
Yes
2 2
No
3 2
Yes