10分RE,TLE求助
查看原帖
10分RE,TLE求助
230804
Durancer楼主2020/9/6 10:23
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int n,m,head[10009],edge_num,v[10009],edge_num1,head1[10009],end_v[10009],ans=10000000;//n个点和,m个边,v用来存自身能到达终点的点的标记,end_v用来存自身和所有出边的终点都能到终点的点的标记 
struct node{
	int last;//该点指向的上一条边, 
	int to;
	int dis; 
};
int diss[10000]; 
node edge[20009];//正着储存 
node edge1[20009];//反向储存 
int Edge1(int from,int to)//正向储存一遍; 
{
		edge[++edge_num].last=head[from];
		edge[edge_num].to=to;
		edge[edge_num].dis=1;
		head[from]=edge_num; 
}
int Edge2(int from,int to)//正向储存一遍; 
{
		edge1[++edge_num1].last=head1[from];
		edge1[edge_num1].to=to;
		edge1[edge_num1].dis=1;
		head1[from]=edge_num1; 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y)
		{
			continue;
		}
		else 
		{
			Edge1(x,y);
			Edge2(y,x);
		}
	}
	int start_map,end_map;
	cin>>start_map>>end_map;
	queue<int>q;
	q.push(end_map);
	v[end_map]=1;//终点一定能到终点 
	while(!q.empty())//找自身可以到达终点的点; 
	{
		int k=q.front();
		q.pop();
		for(int i=head1[k];i!=0;i=edge1[i].last)
		{
			int kk=edge1[i].to;
			if(v[kk]==0)
			{
				q.push(kk);
				v[kk]=1;//若这个点没有被搜过就把他标记为能到终点的点,然后放入队列; 
			}
		}	
	}//到这里是正确的
	for(int i=1;i<=n;i++)
	{
		end_v[i]=1;
	}
	for(int i=1;i<=n;i++)//遍历所有符合自身可以到达终点的点,看看他们的所有出边的点是否也能到达 
	{
		if(v[i]==1)//满足条件 
		{
			for(int k=head[i];k;k=edge[k].last)
			{
				int l=edge[k].to;
				if(v[l]==0)//出边的点中有一个不能连接终点,则不能用 
				{
					end_v[i]=0;
				}
			}
		}
		if(v[i]==0)
		{
			end_v[i]=0;
		}
	} 
	//正确
	if(end_v[start_map]==0)//终点无法连接,直接无解;
	{
		cout<<-1<<endl; 
		return 0;
	}
	if(end_v[start_map]==1)
	{
		queue<int> s;
		s.push(start_map);
		while(!s.empty())
		{
			int al;
			al=s.front();
			s.pop();
			for(int i=head[al];i!=0;i=edge[i].last)
			{
				int zhi;
				zhi=edge[i].to;//该边指向的点
				if(end_v[zhi]==1)//指向的点满足条件 
				{
					diss[zhi]=diss[al]+1;
					s.push(zhi);
					if(diss[end_map]!=0)
					{
						ans=min(ans,diss[end_map]);
					}
				} 
			}
		}
		if(ans==10000000)
		{
			cout<<-1<<endl;
		}
		else cout<<ans<<endl;
	}
	return 0; 
}
2020/9/6 10:23
加载中...