RE 2# 其他AC,悬关求调
查看原帖
RE 2# 其他AC,悬关求调
865625
KobeBeanBryantCox楼主2023/8/2 16:44
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std;
Code by wjb;
const int inf=1000000000;
int n,m,g1[10010],g2[10010],cnt=0,s,t,u[200010],v[200010],fir[10010],nex[200010],c[200010];
bool b[10010];
void add(int u,int v)
{
	nex[++cnt]=fir[u];
	c[cnt]=v;
	fir[u]=cnt;
}
bool check(int flag,int u)
{
	if(flag==1)return true;
	int t=fir[u];
	while(t>0)
	{
		if(g1[c[t]]==inf)return false;
		t=nex[t];
	}
	return true;
}
int spfa(int f[],int flag)
{
	for(int i=1;i<=n;i++)f[i]=inf;
	queue<int>q;
	q.push(s),b[s]=true,f[s]=0;
	while(!q.empty())
	{
		int u=q.front(),t=fir[u];
		while(t>0)
		{
			int v=c[t];
			if(f[v]>f[u]+1&&check(flag,v))
			{
				f[v]=f[u]+1;
				if(!b[v])b[v]=true,q.push(v);
			}
			t=nex[t];
		}
		b[u]=false;
		q.pop();
	}
	if(f[t]==inf)return (-1);
	else return f[t];
}
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&u[i],&v[i]),add(v[i],u[i]);
	scanf("%d%d",&t,&s);
	if(spfa(g1,1)==(-1))cout<<"-1",exit(0);
	swap(s,t);
	memset(fir,0,sizeof(fir));
	memset(nex,0,sizeof(nex));
	memset(c,0,sizeof(c));
	memset(b,false,sizeof(b));
	for(int i=1;i<=m;i++)add(u[i],v[i]);
	cout<<spfa(g2,2);
	return 0;
}
2023/8/2 16:44
加载中...