10分TLEMLE求助
查看原帖
10分TLEMLE求助
355000
N0Name楼主2021/2/3 08:29
#include<iostream>
#include<queue>
#include<cstring>
#define N 10010
using namespace std;
vector<int> G[N];
int s,t,n,m;
int cnt[N],num[N],vis[N];//cnt终点到,num出边 
int dis[N];
void bfs1(int t){
	queue<int>que;
	que.push(t);
	vis[t]=1;
	while(que.size()){
		int x = que.front();
		que.pop();
		for(int i=0;i<G[x].size();i++){
			int y = G[x][i];
			cnt[y]++;
			if(vis[y]==0){
				que.push(y);
			}
		}
	}
}
int bfs2(int t){
	dis[t]=0;
	vis[t]=1;
	queue<int>que;
	que.push(t);
	while(que.size()){
		int x = que.front();
		que.pop();
		for(int i=0;i<G[x].size();i++){
			int y = G[x][i];
			if(vis[y]==0 && cnt[y]==num[y]){
				dis[y] = dis[x] + 1;
				vis[y] =1;
			if(y==s) return dis[s];
				que.push(y);
			} 
		}
	}
	return -1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x!=y){
			num[x]++;
			G[y].push_back(x);	
		}
					
	}
	cin>>s>>t;
	bfs1(t);
	memset(vis,0,sizeof(vis));
	cout<<bfs2(t);
	return 0;
}

求助,Orz

2021/2/3 08:29
加载中...