求救,20分WA
查看原帖
求救,20分WA
547908
NightTide楼主2021/8/9 11:03
#include<bits/stdc++.h>
using namespace std;
struct edge{
	int pre;
	int to;
};
int n,m,s,t;
edge e1[200010],e2[400010];
int cnt1,cnt2,head1[10010],head2[10010],vis[10010];
bool iscon[10010],flag=true;
void add1(int u,int v){
	e1[++cnt1].pre=head1[u];
	e1[cnt1].to=v;
	head1[u]=cnt1;
}
void add2(int u,int v){
	e2[++cnt2].pre=head2[u];
	e2[cnt2].to=v;
	head2[u]=cnt2;
}
void find(int now){
	queue<int> qu;
	qu.push(now);
	iscon[now]=1;
	while(qu.size()){
		int p=qu.front();
		qu.pop();
		for(int i=head2[p];i;i=e2[i].pre){
			if(!iscon[e2[i].to]){
				qu.push(e2[i].to);
				iscon[e2[i].to]=1;
			}
		}
	}
}
void bfs(int now){
	queue<int> qu;
	qu.push(now);
	vis[now]=1;
	while(qu.size()){
		int p=qu.front();
		qu.pop();
		if(p==t){
			cout<<vis[p]-1<<endl;
			flag=false;
			return ;
		}
		for(int i=head1[p];i;i=e1[i].pre){
			if(!vis[e1[i].to]&&iscon[e1[i].to]){
				qu.push(e1[i].to);
				vis[e1[i].to]=vis[p]+1;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0,u,v;i<m;i++){
		scanf("%d%d",&u,&v);
		add1(u,v);
		add2(v,u);
	}
	scanf("%d%d",&s,&t);
	find(t);
	for(int i=1;i<=n;i++){
		if(iscon[i]){
			for(int j=head1[i];j;j=e1[j].pre){
				if(!iscon[e1[j].to]){
					iscon[i]=0;
					break;
				}
			}
		}
	}
	if(!iscon[s]){
		cout<<"-1"<<endl;
	}else{
		bfs(s);
		if(flag){
			cout<<"-1"<<endl;
		}
	}
	return 0;
}

好像错的点全部输出的都是-1,但是样例过了

2021/8/9 11:03
加载中...