简答题
偏难
#22107
加工零件
加工零件



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e5+5;
const int MAXM=2e5+5;
int n,m,que;
int head[MAXN],v[MAXM],next[MAXM],cnt=0;
int dis[MAXN][2];
void add_edge(int s,int t){
v[++cnt]=t;
next[cnt]=head[s];
head[s]=cnt;
}
void spfa(){
//0表示偶数
//1表示奇数
memset(dis,0x3f,sizeof(dis));
dis[1][0]=0;//起始路径0
queue<int> q;//队列实现
q.push(1);
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=next[i]){
int np=v[i];
if(dis[cur][0]+1<dis[np][1] || dis[cur][1]+1<dis[np][0])
q.push(np);
dis[np][1]=min(dis[np][1],dis[cur][0]+1);
dis[np][0]=min(dis[np][0],dis[cur][1]+1);
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&que);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
spfa();
while(que--){
int a,l;
scanf("%d%d",&a,&l);
if(head[1]&&dis[a][l&1]<=l)printf("Yes\n");
else printf("No\n");
}
return 0;
}</pre><p><br/></p>
解析
这道题考察图论的知识运用,是属于最短路径的变形题目,可以利用spfa或Dijkstra来完成,难度较高。
根据性质,工人之间的关系是图。相连接,之间的路径权值是1。加工零件的过程可以相互传递,来回都是偶数次,因此在求个最短路时看奇偶步数内能否可达,要求与L的奇偶性一致。