90分求调
查看原帖
90分求调
1211899
Bobi2014楼主2024/8/23 11:39
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10,M = 2e5 + 10;
struct edge{
	int ed,next;
} b[M];
int n,m,nbs[N],tot,s,t,bis[N];
bool vis[N];
queue<int> q;
void addedge(int u,int v){
	b[++tot].ed = v;b[tot].next = nbs[u];nbs[u] = tot;
}
bool init(int s,int t){
	memset(bis,0,sizeof(bis));
	while(q.empty() == false){
		q.pop();
	}
	q.push(s);
	bis[s] = 1;
	while(q.empty() == false){
		int u = q.front();
		for(int x = nbs[u];x;x = b[x].next){
			int v = b[x].ed;
			if(bis[v] == 0){
				q.push(v);
				bis[v] = 1;
			} 
			if(v == t){
				return true;
			}
		}
		q.pop();
	}
	return false;
}
bool check(int x){
	for(int i = nbs[x];i;i = b[i].next){
		int v = b[i].ed;
		if(vis[v] == false){
			return false;
		}
	} 
	return true;
}
void bfs(){
	memset(bis,127,sizeof(bis));
	while(q.empty() == false){
		q.pop();
	}	
	q.push(s);
	bis[s] = 0;
	while(q.empty() == false){
		int u = q.front();
		if(u == t){
			return;
		}
		for(int x = nbs[u];x;x = b[x].next){
			int v = b[x].ed;
			if(bis[v] > bis[u] + 1 and check(v) == true){
				bis[v] = bis[u] + 1;
				if(v == t){
					return;
				}
				q.push(v);
			}
		}
		q.pop();
	}
}
int read(){
	int ret = 0;
	char ch = getchar();
	while(ch < '0' or ch > '9'){
		ch = getchar();
	}
	while(ch >= '0' and ch <= '9'){
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret;
}
void print(int x){
	if(x == 0){
		return;
	}
	print(x / 10);
	putchar((char)(x % 10 + '0'));
} 
int main(){
	n = read();
	m = read();
	for(int i = 1,u,v;i <= m;i ++){
		u = read();
		v = read();
		addedge(u,v);
	}
	s = read();
	t = read();
	for(int i = 1;i <= n;i ++){
		if(i == t){
			vis[i] = true;
		}else{
			vis[i] = init(i,t);
		}
	}
	if(check(s) == false){
		putchar('-');
		putchar('1');
		return 0;
	}
	bfs();
	if(bis[t] > 1e9){
		putchar('-');
		putchar('1');
	}else{
		print(bis[t]);
	}
	return 0;
}

2024/8/23 11:39
加载中...