70pts求调!谢谢!
查看原帖
70pts求调!谢谢!
749268
tuliwen233楼主2024/11/7 18:17
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2e5+10;
int n,m,head[M],eg,dis[N],hhead[M],eeg;
bool vis[N],f[N],ff[N];//f:是否能到达终点 ff:所有出边的点是否与终点连通 
struct edge{
	int to,nxt;
}e[M],ee[M];//e:正向边 ee:反向边 
struct node{
	int d,x;
	friend bool operator > (node a,node b)
	{
		return a.d>b.d;
	}
};
inline int read()
{
	int x=0,y=1;char c=getchar();
	while(c<'0' || c>'9'){y=c=='-'?-1:y;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*y;
}
void add(int x,int y)
{
	e[++eg].to=y;
	e[eg].nxt=head[x];
	head[x]=eg;
}
void aadd(int x,int y)
{
	ee[++eeg].to=y;
	ee[eeg].nxt=hhead[x];
	hhead[x]=eeg;
}
void dij(int s)
{
	priority_queue<node, vector<node>, greater<node> >q;
	dis[s]=0;
	q.push({dis[s],s});
	while(!q.empty())
	{
		int x=q.top().x;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		if(!ff[x]) continue;
		for(int j=head[x];j;j=e[j].nxt)
		{
			int y=e[j].to;
			if(dis[y]>dis[x]+1)
			{
				dis[y]=dis[x]+1;
				q.push({dis[y],y});
			}
		}
	}
}
void dfs(int x)
{
	if(f[x]) return ;
	f[x]=1;
	for(int i=hhead[x];i;i=ee[i].nxt)
	{
		int y=ee[i].to;
		dfs(y);
	}
	return ;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	memset(dis,0x7f,N);
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int x=read(),y=read();
		add(x,y);
		aadd(y,x);
	}
	int s=read(),t=read();
	dfs(t);
	for(int i=1;i<=n;++i)
	{
		ff[i]=1;
//		cout<<f[i]<<' ';
		for(int j=head[i];j;j=e[j].nxt)
		{
			int y=e[j].to;
			if(!f[y])
			{
				ff[i]=0;
				break;
			}
		}
	}
	if(!ff[s]){printf("-1");return 0;}
	dij(s);
	if(dis[t]==0x7f7f7f7f) printf("-1");
	else printf("%d",dis[t]);
	return 0;
}
2024/11/7 18:17
加载中...