最短路
对于上图,如果我们相知道 $2$ 号工人想要一个 $3$ 阶段的零件,其实是看 $2$ 到 $1$
有没有一条长度为 $3$ 的路径.但如果要求 $4$ 阶段的路径,那就不一定了.
所以我们直接求一遍最短路,分奇最短路和偶最短路.
处理完后,最后一次 $\Theta (1)$ 的回答,如果路径长度过大,就是 $No$,否则就是 $Yes$.
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, x;
// vector 建图
vector<int> g[100005];
struct node {int u, d; // 目标节点,路径长度
};
queue<node> q;
// 根据路径长度来判断奇偶
int dis[100005][2];
void bfs() {memset(dis, 0x3f, sizeof(dis));q.push((node){1, 0});dis[1][0] = 0; // 初始化while (!q.empty()) {node h = q.front();q.pop();int u = h.u, d = h.d;for (int i = 0; i < g[u].size(); i++) { // 枚举这个点相连接的节点int v = g[u][i];if (d + 1 < dis[v][(d+1)%2]) { // 最短路dis[v][(d+1)%2] = d + 1;q.push((node){v, d + 1}); // 放入队列}}}
}
int main() {
// freopen("work.in", "r", stdin);
// freopen("work.out", "w", stdout);scanf("%d%d%d", &n, &m, &x);for (int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}bfs();for (int i = 1; i <= x; i++) {int u, t;scanf("%d%d", &u, &t);// 路径长度合法// t % 2 表示是奇还是偶// 可以接到单子的路径if (dis[u][t%2] >= t) printf("Yes\n");else printf("No\n"); // 路径长度不合法}return 0;
}