CSP-J2019 加工零件

Background：

之前 $noip $死了，泥萌都说 (noip SPFA) 了，现在 (noip) 复活了，所以 (SPFA) 也复活了。

（注:这里的 (noip) 跟 (lxl) 没有任何关系qwq

Description：

原题

简化版题意：

给出无向图，(q) 次询问，每次给定 (A_i, L_i) ，设 (dis_x) 表示点 (x) 与 (1) 号点的距离，求 (dis_{A_i}) 是否与 (dis_{L_i}) 奇偶性相同且 (dis_{A_i}le dis_{L_i})。

Solution：

分奇偶求最短路，单次询问只要 (O(1)) 判断就好了

然后考虑到 (NOI 2019 D1T1) 的教训毅然决然的用了 (SPFA)

(SPFA) 的复杂度是 (O(kE))，(q) 次询问复杂度 (O(q))，总复杂度大概是 (O(kE+q)) (?)

Code：

#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9;
const int N = 1e5+1; 
int n,m,qq;
struct edge
{
	int nxt;
	int to;
	int len;
}e[N*2];
int h[N*2],cnt;
int dis1[N],dis2[N]; //dis1[i]%2==1,dis2[i]%2==0 
int vis1[N],vis2[N];
queue<int> q;

void add(int u,int v)
{
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	e[cnt].len=1;
	h[u]=cnt;
}

void SPFA()
{
	memset(dis1,0x3f,sizeof(dis1));
	memset(dis2,0x3f,sizeof(dis2));
	dis2[1]=0;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(dis1[u]+1<dis2[v]||dis2[u]+1<dis1[v])
			{q.push(v);}
			if(dis1[u]+1<dis2[v])
				dis2[v]=dis1[u]+1;
			if(dis2[u]+1<dis1[v])
				dis1[v]=dis2[u]+1;
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&qq);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	SPFA();
	for(int i=1;i<=qq;++i)
	{
		int ai,li;
		scanf("%d%d",&ai,&li);
		if(li%2==1)
		{
			if(dis1[ai]<=li) printf("Yes
");
			else printf("No
");
		}
		else if(li%2==0)
		{
			if(dis2[ai]<=li) printf("Yes
");
			else printf("No
");
		}
	}
	return 0;
}