[CSP2019]加工零件

第一行两个正整数 𝑛,𝑚 和 𝑞，分别表示工人的数目、传送带的数目和工单的数目。
接下来 𝑚 行，每行两个正整数 𝑢 和 𝑣，表示编号为 𝑢 和 𝑣 的工人之间存在一条零件传输带。保证 𝑢 ≠ 𝑣。
接下来 𝑞 行，每行两个正整数 𝑎 和 𝐿，表示编号为 𝑎 的工人想生产一个第 𝐿 阶段的零件。

共 𝑞 行，每行一个字符串 “Yes” 或者 “No”。如果按照第 𝑖 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 𝑖 行输出 “Yes”；否则在第 𝑖 行输出 “No”。注意输出不含引号。

Pascal(fpc 3.0.2) 解法, 执行用时: 91ms, 内存消耗: 4700K, 提交时间: 2019-11-19 18:26:06

var a,b,c,d,e:array[0..300001] of longint;
f:array[0..300001,0..1] of boolean;
g:array[0..300001,0..1] of longint;
i,n,m,k,x,y,t,w,cnt:longint;
begin
readln(n,m,k);
for i:=1 to m do
  begin
  readln(x,y);
  inc(cnt);a[cnt]:=y;b[cnt]:=c[x];c[x]:=cnt;
  inc(cnt);a[cnt]:=x;b[cnt]:=c[y];c[y]:=cnt;
  end;
t:=1;w:=1;e[1]:=1;d[1]:=0;f[1,0]:=true;g[1,0]:=0;
while t<=w do
  begin
  i:=c[e[t]];
  while i<>0 do
    begin
    if f[a[i],1-d[t]]=false then
      begin
      f[a[i],1-d[t]]:=true;
      w:=w+1;e[w]:=a[i];d[w]:=1-d[t];
      g[e[w],d[w]]:=g[e[t],d[t]]+1;
      end;
    i:=b[i];
    end;
  inc(t);
  end;
for i:=1 to k do
  begin
  readln(x,y);
  if f[x,y mod 2] and (g[x,y mod 2]<=y) then
    writeln('Yes')
  else writeln('No');
  end;
end.

C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 5408K, 提交时间: 2019-11-21 12:31:05

#include<cstdio>
#include<cstring>
#define mx 200005
int n,m,q,he[mx],to[mx],nx[mx],qw[mx],qh[mx],l,r,ds[mx][2];
inline void wk(int wz,int x,int y)
{to[wz]=y,nx[wz]=he[x],he[x]=wz;}
int main()
{
//	freopen("work.in","r",stdin);
//	freopen("work.out","w",stdout);
	memset(ds,0x3f,sizeof(ds));
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,x,y;i<=m;++i)
		scanf("%d%d",&x,&y),wk(i<<1,x,y),wk(i<<1|1,y,x);
	ds[1][0]=0,qw[++r]=1,qh[r]=0;
	while(l<r)
	{
		++l;int x=qw[l],y=qh[l];
		for(int i=he[x];i;i=nx[i])
		{
			if(ds[to[i]][y^1]>1e9)
				ds[to[i]][y^1]=ds[x][y]+1,
				qw[++r]=to[i],qh[r]=y^1;
		}
	}
	for(int i=1,x,y,op;i<=q;++i)
	{
		scanf("%d%d",&x,&y),op=y&1;
		if(y<ds[x][op]) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

C++ 解法, 执行用时: 51ms, 内存消耗: 5752K, 提交时间: 2021-10-30 16:02:41

#include <iostream>
#include <cstring>
using namespace std;
const int N=220000;
int n,m,q,x,y,i,t,w,a[N],b[N],c[N],e[N],g[N],f[N][2],cnt;
int main(){
	memset(f,0x3f,sizeof(f));
	scanf("%d%d%d",&n,&m,&q);
	for (i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		a[++cnt]=y;b[cnt]=c[x];c[x]=cnt;
		a[++cnt]=x;b[cnt]=c[y];c[y]=cnt;	
	}	
	t=1;w=1;e[1]=1;g[1]=0;f[1][0]=0;
	while (t<=w){
		i=c[e[t]];
		while (i!=0){
			if (f[a[i]][g[t]^1]>f[e[t]][g[t]]+1){
				f[a[i]][g[t]^1]=f[e[t]][g[t]]+1;
				w++;e[w]=a[i];g[w]=g[t]^1;
			} 	
			i=b[i];
		}
		t++;
	} 
	for (i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		if (f[x][y%2]<=y) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

详情