10分求助
查看原帖
10分求助
1067988
Raymond2014楼主2025/1/23 20:44

写的要死要活,结果只拿了10分……😭😭😭

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+1;
vector<int> vec1[N],vec2[N];
int d[N],trash[N],vis[N],n,m,s,t;
void dfs(int u){
	for(auto v:vec2[u]){
		if(vis[v]==0){
			vis[v]=1;
			dfs(v);
		}
	}
}
bool check(int u){
	for(auto v:vec1[u])
		if(vis[v]==0) return true;
	return false;
}
void bfs(){
	memset(vis,0,sizeof(vis));
	memset(d,-1,sizeof(d));
	queue<int> q;
	q.push(s);
	d[s]=0;
	vis[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		if(u==t) return;
		for(auto v:vec1[u]){
			if(!vis[v] && !trash[v]){
				vis[v]=1;
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		vec1[a].push_back(b);
		vec2[b].push_back(a);
	}
	cin>>s>>t;
	dfs(t);
	for(int i=1;i<=n;i++){
		if(vis[i]=1){
			if(check(i)) trash[i]=1;
		}
		else if(vis[i]==0) trash[i]=1;
	}
	bfs();
	cout<<d[t];
	return 0;
}

2025/1/23 20:44
加载中...