bfs20pts WA 求助
查看原帖
bfs20pts WA 求助
553904
yingbowen楼主2022/10/4 10:45
#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];//第i条边能否到终点 
int used_point[200005];//第i个点是否走过,用于bfs 
int acc_point[200005];//第i个点能否经过 
int nused[200005];//第i个点是否走过,用于bbfs
int ans = 0x7f7f7f7f;//答案

int stk[2000005];//bfs的栈 
int stp[2000005];//栈的第i个元素的步数 
int l = 1;//l
int r = 0;//r
bool ok = 0;//有没有做好
int uused[2000005];//第i个点是否走过
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){//从终点bfs,为了算出第i个边能否走
	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(){//通过bfs得到的边计算第i个点能否经过
	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(){//20pts的bfs
	if(l > r)return;//如果没队列里没东西了就结束
	int pt = stk[l];//当前点 
	int sp = stp[l++];//当前步数
	for(int i = head1[pt];i;i=nxt1[i]){//遍历所有边
		int gt = e1[i];//gt为下一个点
		if(gt == t){//如果是终点就直接输出步
			cout << sp+1;
			ok = 1;
			return;
		}
		if(acc_point[gt] == 0)continue;//如果这个点不被允许就跳过 
		if(uused[pt] != 1){//如果这个点没被走过
			uused[pt] = 1;//设置为走过 
			r++;//r++;
			stk[r] = gt;//队列里加新的元素
			stp[r] = sp+1;//step++;
		}
	}
	bbfs();//继续
}
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();
	
	r++;//bbfs
	stk[r] = s;
	stp[r] = 0;
	bbfs();
	if(ok == 0){
		cout << -1; 
	}
	return 0;
}

改bfs20分

2022/10/4 10:45
加载中...