30pts求助bfs,悬关
查看原帖
30pts求助bfs,悬关
780539
qwertim楼主2023/6/8 13:19

rt.

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,m,u,v,s,t;
int cnt,to[200005],last[10005],ne[200005];
int to2[200005],last2[10005],ne2[200005];
bool vis[10005],b[10005],vis2[10005];
void add(int x,int y){
	to[++cnt]=y,ne[cnt]=last[x],last[x]=cnt;
	to2[cnt]=x,ne2[cnt]=last2[y],last2[y]=cnt;
}
void dfs(int x){
	vis[x]=1,b[x]=1;
	for(int i=last2[x];i!=0;i=ne2[i]){
		int y=to2[i];
		if(!vis[y])dfs(y);
	}
}
void bfs(){
	queue<pair<int,int>>q;
	q.push({0,1});
	while(q.size()){
		int step=q.front().first+1,x=q.front().second;
		q.pop();
		for(int i=last[x];i!=0;i=ne[i]){
			int y=to[i];
			if(y==t){
				cout<<step;
				return;
			}
			if(!vis2[y]&&b[y]){
				vis2[y]=1;
				q.push({step,y});
			}
		}
	}
	cout<<-1;
}
int main(){
	cin>>n>>m;
	fo(i,1,m){
		scanf("%d %d",&u,&v);
		if(u!=v)add(u,v);
	}
	cin>>s>>t;
	dfs(t);
	if(!vis[s])return cout<<-1,0;
	fo(i,1,n)
		if(vis[i])
			for(int j=last[i];j!=0;j=ne[j])
				if(!vis[to[j]])b[i]=0;
	if(!b[s])return cout<<-1,0;
	bfs();
	return 0;
}

貌似是 bfs 的问题。

2023/6/8 13:19
加载中...