求助!60pts
查看原帖
求助!60pts
1164775
Jadonyzx楼主2024/2/26 20:20
#include<bits/stdc++.h>
#define maxn 10010
#define maxm 200010
#define inf 114514
#define int long long
using namespace std;
int n,m,st,en,edgecnt,edge_cnt;
struct EDGE{
	int to,next;
}edge[maxm*2],ed_ge[maxm*2];
int head[maxn],dep[maxn],vis[maxn],he_ad[maxn];
bool cango[maxn],allcango[maxn];
queue<int>q;
void addedge(int from,int to){
	edge[++edgecnt].next=head[from];
	edge[edgecnt].to=to;
	head[from]=edgecnt;
	return;
}
void add_edge(int from,int to){
	ed_ge[++edge_cnt].next=he_ad[from];
	ed_ge[edge_cnt].to=to;
	he_ad[from]=edge_cnt;
	return;
}
signed main(){
	cin>>n>>m;
	for(int i = 1;i <= m;++i)
	{
		int u,v;
		cin>>u>>v;
		if(u==v) continue;
		add_edge(v,u);
		addedge(u,v);
	}
	cin>>st>>en;
	q.push(en);
	memset(dep,inf,sizeof(dep));
	dep[st]=0;
	q.push(en);
	cango[en]=1;
	while(!q.empty()){
		int now=q.front();q.pop();
		vis[now]=1;
		for(int ioi=he_ad[now];ioi;ioi=ed_ge[ioi].next){
			int v=ed_ge[ioi].to;
			if(!vis[v]){
				q.push(v);
				cango[v]=1;
			}
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i){
		//cout<<cango[i]<<' ';
		allcango[i]=1;
		if(!cango[i]){
			allcango[i]=0;
			continue;
		}
		for(int ioi=head[i];ioi;ioi=edge[ioi].next){
			int v=edge[ioi].to;
			if(!cango[v]){
				allcango[i]=0;
				break;
			}
		}
	}
	if(!cango[st] || !allcango[st]){
		cout<<-1;
		return 0;
	}
	while(!q.empty())q.pop();
	q.push(st);
	while(!q.empty()){
		int now=q.front();q.pop();
		vis[now]=1;
		for(int ccf=head[now];ccf;ccf=edge[ccf].next){
			int v=edge[ccf].to;
			if(allcango[v] && !vis[v]){
				dep[v]=dep[now]+1;
				q.push(v);
			}
		}
	}
	if(dep[en]>=inf-114) cout<<-1;
	else cout<<dep[en];
	return 0;
}
2024/2/26 20:20
加载中...