10pts求助(悬赏关注)
查看原帖
10pts求助(悬赏关注)
553904
yingbowen楼主2022/10/3 21:17
#include <bits/stdc++.h>
using namespace std;
int n,m;
int s,t;
int e1[200005];
int nxt1[200005];
int head1[200005];
int cnt1 = 0;

int e2[200005];
int nxt2[200005];
int head2[200005];
int cnt2 = 0;

int acc[200005];
int used_point[200005];
int acc_point[200005];
int nused[200005];
struct point{
	int num,dis;
};
int ans = 0x7f;
bool ok = 0;
void addEdge1(int a,int b){
	cnt1++;
	e1[cnt1] = b;
	nxt1[cnt1] = head1[a];
	head1[a] = cnt1;
}
void addEdge2(int a,int b){
	cnt2++;
	e2[cnt2] = b;
	nxt2[cnt2] = head2[a];
	head2[a] = cnt2;
}
void bfs(int pt){
	used_point[pt] = 1;
	for(int i = head2[pt];i;i=nxt2[i]){
		int gt = e2[i];
		acc[i] = 1;
		if(used_point[gt])continue;
		bfs(gt);
	}
}
void Ac_point(){
	for(int i = 1;i<=n;i++){
		acc_point[i] = 1;
		for(int j = head1[i];j;j=nxt1[j]){
			if(acc[j] == 0){
				acc_point[i] = 0;
				break;
			}
		}
	}
}
void bbfs(int pt,int step){
	if(step > ans)return;
	nused[pt] = 1;
	for(int i = head1[pt];i;i=nxt1[pt]){
		int gt = e1[i];
		if(nused[gt] == 1)continue;
		if(acc_point[gt] == 0)continue;
		if(gt == t){
			ans = min(ans,step+1);
			return;
		}
		bbfs(gt,step+1);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1;i<=m;i++){
		int a,b;
		cin >> a >> b;
		if(a == b)continue; 
		addEdge1(a,b);
		addEdge2(b,a);
	}
	cin >> s >> t;
	bfs(t);
	Ac_point();
	bbfs(s,0);
	if(ans == 0x7f7f7f7f)cout << -1;
	else cout << ans;
	return 0;
}
2022/10/3 21:17
加载中...