10分TLE,MLE求助
查看原帖
10分TLE,MLE求助
252551
Xqbk楼主2020/10/25 17:35
#include<iostream>
#include<queue>
using namespace std;
int n,m,s,t,flag=0,ans;
int u[200001],v[200001];
int b[10001],b2[10001];
int dis[10001];
queue<int> q;
void dfs(int p)
{
	if(b[p])
	{
		return;
	}
	for(int i=0;i<m;i++)
	{
		if(v[i]==p&&v[i]!=u[i])
		{
			dfs(u[i]);
		}
	}
	b[p]=1;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>u[i]>>v[i];
	}
	cin>>s>>t;
	dfs(t);
	for(int i=0;i<m;i++)
	{
		if(b[v[i]]==0&&b[u[i]]!=0)
		{
			b[u[i]]=-1;
		}
	}
	if(b[s])
	{
		q.push(s);
	}
	dis[s]=0;
	b2[s]=1;
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		if(p==t)
		{
			flag=1;
			ans=dis[p];
			break;
		}
		for(int i=0;i<m;i++)
		{
			if(u[i]==p&&!b2[v[i]]&&b[v[i]]>0)
			{
				q.push(v[i]);
				dis[v[i]]=dis[p]+1;
				b2[v[i]]=1;
			}
		}
	}
	if(flag)
	{
		cout<<ans;
	}
	else
	{
		cout<<-1;
	}
	return 0;
}
2020/10/25 17:35
加载中...