两遍dfs加一遍最短路20ptsMLE
查看原帖
两遍dfs加一遍最短路20ptsMLE
1075989
BlauAnthony楼主2025/7/28 14:15
#include<iostream>
using namespace std;
const int maxn=10001,maxm=200001,inf=2147483647;
int n,m,s,t;
int h[maxn],nxt[maxm],to[maxm],opt;
void add(int u,int v){
	nxt[++opt]=h[u];
	h[u]=opt;
	to[opt]=v;
}
int vis[maxn],can[maxn];
bool dfs1(int node,int fa){
	if(can[node])return 1;
	for(int i=h[node];i;i=nxt[i]){
		if(to[i]==fa)continue;
		if(dfs1(to[i],node))can[node]=1;
	}
	if(can[node])return 1;
	return 0;
}
void dfs2(int node,int fa){
	int res=0,all=0;
	for(int i=h[node];i;i=nxt[i]){
		if(to[i]==fa)continue;
		if(can[to[i]])res++;
		dfs2(to[i],node);
		all++;
	}
	if(res==all&&res>0)vis[node]=1;
}
int v[maxn],dist[maxn];
void dijkstra(){
	dist[s]=0;
	int step=-1,minnum;
	while(!v[t]){
		minnum=inf;
		for(int i=1;i<=n;i++){
			if(!v[i]&&vis[i]&&dist[i]<minnum){
				minnum=dist[i];
				step=i;
			}
		}
		if(step==-1)return;
		v[step]=1;
		for(int i=h[step];i;i=nxt[i]){
			if(!vis[to[i]])continue;
			if(dist[to[i]]>dist[step]+1){
				dist[to[i]]=dist[step]+1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0,x,y;i<m;i++){
		cin>>x>>y;
		add(x,y);
	}
	cin>>s>>t;
	vis[t]=can[t]=1;
	dfs1(s,0);
	dfs2(s,0);
	for(int i=1;i<=n;i++)dist[i]=inf;
	dijkstra();
	cout<<(dist[t]==inf?-1:dist[t]);
	return 0;
}

死亡回放

2025/7/28 14:15
加载中...