简答题 偏难
#22107

加工零件

加工零件


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;queue&gt; #include&lt;cstring&gt; #include&lt;cstdio&gt; 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&lt;int&gt; 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&lt;dis[np][1] || dis[cur][1]+1&lt;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",&amp;n,&amp;m,&amp;que);        for(int i=0;i&lt;m;i++){               int u,v;               scanf("%d%d",&amp;u,&amp;v);               add_edge(u,v);               add_edge(v,u);        }        spfa();        while(que--){               int a,l;               scanf("%d%d",&amp;a,&amp;l);               if(head[1]&amp;&amp;dis[a][l&amp;1]&lt;=l)printf("Yes\n");               else printf("No\n");        }        return 0; }</pre><p><br/></p>
解析

这道题考察图论的知识运用,是属于最短路径的变形题目,可以利用spfa或Dijkstra来完成,难度较高。

根据性质,工人之间的关系是图。相连接,之间的路径权值是1。加工零件的过程可以相互传递,来回都是偶数次,因此在求个最短路时看奇偶步数内能否可达,要求与L的奇偶性一致。