#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 5000005; int n, m, c, head[1000005], cnt, dis[1000005][2]; bool vis[1000005][2]; struct node { int data, dis; bool operator < (const node &a) const { return a.dis < dis; } }; priority_queue<node> q; struct Edge { int to, next; }e[1000005]; void add(int u, int v) { e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } void Initialization(void) { memset(dis, 0x3f, sizeof(dis)); q.push((node) {1, 0}); dis[1][0] = 0; } void dijkstra(void) { while (!q.empty()) { node tmp = q.top(); q.pop(); int now = tmp.data; for (int i = head[now]; i; i = e[i].next) { int y = e[i].to; if (dis[y][0] > dis[now][1] + 1) { dis[y][0] = dis[now][1] + 1; if (!vis[y][0]) { vis[y][0] = 1; q.push((node) {y, dis[y][0]}); } } if (dis[y][1] > dis[now][0] + 1) { dis[y][1] = dis[now][0] + 1; if (!vis[y][1]) { vis[y][1] = 1; q.push((node) {y, dis[y][1]}); } } } } } int main(void) { ios::sync_with_stdio(false); cin >> n >> m >> c; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; add(u, v); add(v, u); } Initialization(); dijkstra(); while (c--) { int a, l; cin >> a >> l; if (!head[1]) { cout << "No" << endl; } else if (dis[a][l % 2] <= l) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }

针对题意，原材料相当于第0阶段的零件、我们先假设1号工人轩轩与其他工人之间没有传送带的情况，那么显然，这种情况下，轩轩无法生产任何零件和原料，也不需要给其它工人提供原材料，答案显然是NO。 假设现在1号工人轩轩和i号工人有连边(双向传送带)，那么当i号工人需要生产第1、3、5、7……2k+1阶段的零件的时候，1号工人轩轩分别需要提供第0(原材料)、2、4、6……2k阶段的零件，紧接着i号工人要提供给1号工人轩轩(总数量-2个)奇数阶段的零件，我们发现针对每一个奇数阶段的零件，轩轩都需要提供原材料。 当i号工人想生产偶数阶段的零件时，轩轩需要提供奇数阶段的零件，而如果1号工人轩轩需要偶数阶段的零件，那么i号工人需要提供奇数阶段的零件。 我们将之扩大为一条链： 偶数阶段 奇数阶段 偶数阶段 奇数阶段 距离0 距离1 距离2 距离3 假设i号工人需要生产 L(L>0)阶段的零件 那么只要i->1之间存在一条长度<=L并且和L的奇偶性相同的路径，1号工人就必须生产原材料。 因此：对于一条双向边 1<--->U 我们将每个点1、U分别拆成两的点(奇点和偶点)，边分解为交叉边，生成一张新图，对于新图: 所有从1(0)走向u(0)的路径，对应在原图中就是一条L为偶数的路径。 所有从1(0)走向u(1)的路径，对应在原图中就是一条L为奇数的路径。 为了降低复杂度，我们可以查找： 所有从1(0)走向u(0)的最短路径dist[u][0]，所有从1(0)走向u(1)的最短路径dist[u][1]。问题就转化为单源最短路问题： 对于每次查询的A和 L 我们只需要做如下判断 L是偶数：则只要L>=dist[A][0]; L是奇数：则只要L>=dist[A][1]; AC代码 1.BFS(广度优先搜索) 2.DIJKSTRA(迪杰斯特拉算法) 3.SPFA(队列优化算法)

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 5000005; int n, m, c, head[1000005], cnt, dis[1000005][2]; bool vis[1000005][2]; struct node { int data, dis; bool operator < (const node &a) const { return a.dis < dis; } }; priority_queue<node> q; struct Edge { int to, next; }e[1000005]; void add(int u, int v) { e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } void Initialization(void) { memset(dis, 0x3f, sizeof(dis)); q.push((node) {1, 0}); dis[1][0] = 0; } void dijkstra(void) { while (!q.empty()) { node tmp = q.top(); q.pop(); int now = tmp.data; for (int i = head[now]; i; i = e[i].next) { int y = e[i].to; if (dis[y][0] > dis[now][1] + 1) { dis[y][0] = dis[now][1] + 1; if (!vis[y][0]) { vis[y][0] = 1; q.push((node) {y, dis[y][0]}); } } if (dis[y][1] > dis[now][0] + 1) { dis[y][1] = dis[now][0] + 1; if (!vis[y][1]) { vis[y][1] = 1; q.push((node) {y, dis[y][1]}); } } } } } int main(void) { ios::sync_with_stdio(false); cin >> n >> m >> c; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; add(u, v); add(v, u); } Initialization(); dijkstra(); while (c--) { int a, l; cin >> a >> l; if (!head[1]) { cout << "No" << endl; } else if (dis[a][l % 2] <= l) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }

如果A想生产L阶段(L≥2)的零件，就需要B生产L−1阶段的零件,就需要A生产L−2阶段的零件。 所以只要一个节点生产L阶段的零件需要节点1提供原材料,这个节点生产L+2阶段的零件也需要。 所以我们记录一个点生产奇数与偶数阶段的零件,需不需要节点1提供原材料,以及L分别至少为多少就可以了。 当1是孤立点,即没有连接它的边时,如果1需要生产L阶段的零件,就没有人需要生产L−1,L−2,...,0阶段的零件,所以要输出NO。

感觉比CSP-J2023的压轴题简单好多（悲） 我只是一个初学者，代码不太好看，但能AC 思路： a为1a为1a为1 a非1a非1a非1 节点1“脱网”节点1“脱网”节点1“脱网” NoNoNo NoNoNo 节点1不“脱网”节点1不“脱网”节点1不“脱网” 当l为偶数时Yes,奇数时l>=(1的最小奇数环步数)则Yes,否则No当l为偶数时Yes,奇数时l>=(1的最小奇数环步数)则Yes,否则No当l为偶数时Yes,奇数时l>=(1的最小奇数环步数)则Yes,否则No 当l为偶数时l>=(1至a的最短偶数路径)或者当l为奇数时l>=(1至a的最短奇数路径)时为Yes，否则No当l为偶数时l>=(1至a的最短偶数路径)或者当l为奇数时l>=(1至a的最短奇数路径)时为Yes，否则No当l为偶数时l>=(1至a的最短偶数路径)或者当l为奇数时l>=(1至a的最短奇数路径)时为Yes，否则No

#include <iostream> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int MAXNMQ=100005; vector<int> s[MAXNMQ]; int dp[MAXNMQ][2]; //分两种情况，为奇数时的最小距离[1]和偶数时的最小距离[0] int queue[MAXNMQ*10][2], head=0, tail=1; int main(){ int n, m, q, u, v; cin >> n >> m >> q; for(int i=1;i<=m;i++){ cin >> u >> v; s[u].push_back(v); s[v].push_back(u); } // 初始条件：dp[1]={0,1} // 搜索条件：dp[v][(dp[u]+1)%2]-1 // 队列格式：{v,dp[u]+1} memset(dp, -1, sizeof(dp)); dp[1][0]=0, dp[1][1]=-1; // 初始队列：1的邻居 for(int i=0;i<s[1].size();i++){ queue[tail][0]=s[1][i], queue[tail][1]=1; tail++,tail%=MAXNMQ*10; } // 广搜最短路 while(head!=tail){ int v=queue[head][0], st=queue[head][1]; dp[v][st%2]=st; for(int i=0;i<s[v].size();i++) if(dp[s[v][i]][(st+1)%2]-1){ queue[tail][0]=s[v][i], queue[tail][1]=st+1; tail++,tail%=MAXNMQ10; } head++,head%=MAXNMQ10; } }

#include <bits/stdc++.h> using namespace std; const int M=1e6+10; typedef pair<int,int>PII; int n,m,q; int dist[M][2],ne[M],e[M],h[M],idx; bool st[M][2]; void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1][0]=0; priority_queue<PII,vector<PII>,greater<PII>>heap; heap.push({0,1}); while(heap.size()){ auto p=heap.top(); heap.pop(); int ver=p.second; for(int i=h[ver];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j][0]>dist[ver][1]+1){ dist[j][0]=dist[ver][1]+1; if(!st[j][0]){ heap.push({dist[j][0],j}); st[j][0]=true; } }else if(dist[j][1]>dist[ver][0]+1){ dist[j][1]=dist[ver][0] + 1; if(!st[j][1]){ heap.push({dist[j][1],j}); st[j][1]=true; } } int main(){ memset(h,-1,sizeof h); cin>>n>>m>>q; for(int i=0;i<m;i++){ int u,v; cin>>u>>v; add(v,u); add(u,v); } dijkstra(); while(q--){ int t,l; cin>>t>>l; if(l&1){ if(dist[t][1]<=l){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } }else{ if(dist[t][0]<=l){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } }