[原题传送门](https://www.luogu.com.cn/problem/P5663 "原题传送门") ### 分析 设工人x离工人1的最短路径为d，则工人x生产d阶段的零件，工人1就需要提供原料。如果d是奇数，那么工人x生产大于等于d的奇数的阶段的零件，则工人1就需要提供原料；d如果是偶数也是一样的规律。如果工人x离工人1有奇数最短距离d1，偶数最短距离d2，那么工人x生产大于等于d1的奇数的阶段零件和生产大于等于d2的偶数的阶段零件，则工人1就需要提供原料。 注意：工人1自身离自己有一个d=0的最短距离，所以工人1生产偶数的阶段零件，工人1就需要提供原料。 所以我们需要计算出1到每个点的奇数最短路和偶数最短路。 ### 代码 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+10; const int INF = 0x3f3f3f3f; vector<int> g[N];//存边 int d[N][3];//d[i][1]:表示i点到1的奇数最短路，d[i][2] :表示i点到1的偶数最短路 void bfs() { queue<int> q; q.push(1); memset(d,INF,sizeof(d));//初始化 d[1][1]=INF,d[1][2]=0;//1到1的偶数最短距离是0 while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(d[v][1]>d[u][2]+1||d[v][2]>d[u][1]+1)//最短距离有更新，就入队 { if(d[v][1]>d[u][2]+1) d[v][1]=d[u][2]+1; if(d[v][2]>d[u][1]+1) d[v][2]=d[u][1]+1; q.push(v); } } } } int main() { int n,m,q; scanf("%d%d%d",&n,&m,&q); int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } bfs(); for(int i=1;i<=q;i++) { scanf("%d%d",&a,&b); if(b%2) { if(d[a][1]<=b) printf("Yes\n"); else printf("No\n"); } else { if(d[a][2]<=b) printf("Yes\n"); else printf("No\n"); } } return 0; } ```