一个点T求优化
查看原帖
一个点T求优化
358794
Xfer_splendor楼主2021/10/2 20:10

RT

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define N 200010
vector<int>s1[N/2];
vector<int>s2[N/2];
int n,m,s,t,u,v,vis[N],f[N];
void dfs (int x){
	//第一遍标记 
	if (vis[x]) return ;
    int ver;
	vis[x]=1;
	for (int i=0;i<s1[x].size();++i){
		ver=s1[x][i];
		dfs (ver);
	}
}
void DFS(int x,int sum){
	//第二遍搜最短路 
	if (f[x]>sum) f[x]=sum;
	else return; 
	int ver;
	for (int i=0;i<s2[x].size();++i){
		ver=s2[x][i];
		if (!vis[ver]) return;
	}
	for (int i=0;i<s2[x].size();++i){
		ver=s2[x][i];
		DFS (ver,sum+1);
	}
}
int main (){
	scanf ("%d%d",&n,&m);
	for (int i=1;i<=m;++i){
		scanf ("%d%d",&u,&v);
		//建边
		s2[u].push_back(v);
		s1[v].push_back(u);
	}
	scanf ("%d%d",&s,&t);
	//第一遍反向搜 
	dfs (t);
	if (!vis[s]){
		printf ("-1");
		return 0;
	}
	memset (f,0x7f,sizeof (f));
	//第二遍 
	DFS (s,0);
	printf ("%d",f[t]);
	return 0;
}
2021/10/2 20:10
加载中...