反向建边两遍BFS,MLE+#10TLE,求调
查看原帖
反向建边两遍BFS,MLE+#10TLE,求调
1400503
lllyyykkk楼主2024/10/11 07:55
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,s,e,dis[10010];
vector<int>ve[10010],fve[10010];
bool flag[10010],vis[10010];
queue<int>q;
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		if(x==y) continue;
		ve[x].push_back(y),fve[y].push_back(x);
	}
	s=read(),e=read();
	q.push(e),flag[e]=1;
	while(!q.empty()){
		int tmp=q.front();q.pop();
		for(auto v:fve[tmp]) if(!flag[v]) flag[v]=1,q.push(v);
	}
	if(!flag[s]){puts("-1");return 0;}
	for(int i=1;i<=n;i++){
		if(flag[i]){
			bool f=1;
			for(auto v:ve[i]) if(!flag[v]){f=0;break;}
			vis[i]=f;
		}
	}
	if(!vis[s]){puts("-1");return 0;}
	q.push(s);dis[s]=0;
	while(!q.empty()){
		int tmp=q.front();q.pop();
		if(tmp==e){cout <<dis[tmp]<<endl;return 0;}
		for(auto v:ve[tmp]) if(vis[v]) dis[v]=dis[tmp]+1,q.push(v);
	}
	puts("-1");
	return 0;
}
2024/10/11 07:55
加载中...