厌氧代码求挑刺
查看原帖
厌氧代码求挑刺
1163238
YWHHDJSer楼主2024/8/13 18:00

RT。不吸氧AC,吸氧只过Hack。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,u,v,f[20002],g,bn,ed,d[20002],t[20002],s;
bool can[20002],e[20002];
struct node
{
	int h,to;
}pic[400004],way[400004];
il void ndin(int x,int y)
{
	g++;
	way[g].to=y;
	way[g].h=f[x];
	f[x]=g;
	s++;
	pic[s].to=x;
	pic[s].h=t[y];
	t[y]=s;
}
il void tpst(int x)
{
	queue<int>que;
	memset(d,inf,sizeof(d));
	que.push(x);
	d[x]=0;
	while(!que.empty())
	{
		ri y=que.front();
		que.pop();
		e[y]=true;
		for(ri i=t[y];i;i=pic[i].h)
		{
			ri z=pic[i].to;
			if(d[z]>d[y]+1)
			{
				d[z]=d[y]+1;
				if(!e[z])
				{
					que.push(z);
				}
			}
		}
	}
	for(ri i=1;i<=a;i++)
	{
		if(d[i]!=inf)
		{
			register bool ck=true;
			for(ri j=f[i];j;j=way[j].h)
			{
				if(d[way[j].to]==inf)
				{
					ck=false;
					break;
				}
			}
			can[i]=ck;
		}
	}
}
il void dijkstra(int x)
{
	queue<int>que;
	memset(d,inf,sizeof(d));
	memset(e,false,sizeof(d));
	if(!can[x])
	{
		return;
	}
	que.push(x);
	d[x]=0;
	while(!que.empty())
	{
		ri y=que.front();
		que.pop();
		e[y]=true;
		for(ri i=f[y];i;i=way[i].h)
		{
			ri z=way[i].to;
			if(can[z]&&d[z]>d[y]+1)
			{
				d[z]=d[y]+1;
				if(!e[z])
				{
					que.push(z);
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&a,&b);
	for(ri i=1;i<=b;i++)
	{
		scanf("%d%d",&u,&v);
		ndin(u,v);
	}
	scanf("%d%d",&bn,&ed);
	tpst(ed);
	dijkstra(bn);
	if(d[ed]==inf)
	{
		puts("-1");
	}
	else
	{
		printf("%d",d[ed]);
	}
	return 0;
}
2024/8/13 18:00
加载中...