70分bfs,求调
查看原帖
70分bfs,求调
1050788
DYH_bubble楼主2024/7/11 22:39

调了好久,样例全过,70分……

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,u,o,c,s,t;
bool ans[10001],law[10001],inlaw[10001];
int dis[10001];
vector<int> v[10001],b[10001];
int bfs(int s){
	memset(ans,0,sizeof(ans));
	memset(dis,0,sizeof(dis));
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int d=q.front();
		q.pop();
		ans[d]=1;
		law[d]=1;
		for(int i=0;i<b[d].size();i++){
			if(!ans[b[d][i]]) q.push(b[d][i]),dis[b[d][i]]=dis[d]+1;
		}
	}
	return 1;
}
int bfs2(int s){
	memset(ans,0,sizeof(ans));
	memset(dis,0,sizeof(dis));
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int d=q.front();
		q.pop();
		ans[d]=1;
		if(inlaw[d]) continue;
		if(d==t) return dis[d];
		for(int i=0;i<v[d].size();i++){
			if(!ans[v[d][i]]&&!inlaw[v[d][i]]) q.push(v[d][i]),dis[v[d][i]]=dis[d]+1;
		}
	}
	return -1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>o;
		v[u].push_back(o);
		b[o].push_back(u);
	}
	cin>>s>>t;
	bfs(t);
	for(int i=1;i<=n;i++){
		if(!law[i]){
			inlaw[i]=1;
			for(int j=0;j<b[i].size();j++){
				inlaw[b[i][j]]=1;
			}
		}
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<i<<':'<<inlaw[i]<<endl;
	}
	*/
	cout<<bfs2(s);
 	return 0;
}

2024/7/11 22:39
加载中...