30分求助
查看原帖
30分求助
64976
hewo楼主2021/9/22 21:47

错的全输出-1去了,改了很久也没看出来为什么

#include<bits/stdc++.h>

using namespace std;

const int MX=3*1000000+1000;
const int ME=4*1000000+1000;
#define LL long long
#define inf 0x3f3f3f3f

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m;

struct tEdge
{
	int to,value;
	int next;
}edge[ME];
int head[MX],cnt=0;

inline void add(int from,int to)
{
	edge[++cnt].to=to,edge[cnt].next=head[from];
	head[from]=cnt;
}

struct tBack
{
	int to,value;
	int next;
}bedge[ME];
int bhead[MX],bcnt=0;	

inline void eback_add(int from,int to)
{
	bedge[++bcnt].to=to,bedge[bcnt].next=bhead[from];
	bhead[from]=bcnt;
}

int S,T;

bool lt[MX];

inline void dfs(int now)
{
	//printf("now: %d\n",now);
	//if(lt[now]) return ;
	for(int i=bhead[now];i;i=bedge[i].next)
	{
		int yt=bedge[i].to;
		//printf("yt: %d\n",yt);
		if(lt[yt]) return ;
		lt[yt]=1;
		dfs(yt);
	}
}

bool alo[MX];

int f[MX];

inline int solve(int now)
{
	if(f[now]!=-1) return f[now];
	if(now==T)
	{
		f[now]=0;
		return f[now];
	}
	for(int i=head[now];i;i=edge[i].next)
	{
		int yt=edge[i].to;
		if(!alo[yt]) continue;
		f[now]=inf;
		f[now]=min(f[now],solve(yt)+1);
	}
	return f[now];
}

int main(int argc, char const *argv[])
{
	//freopen("debug.in","r",stdin);
	n=read(),m=read();
	for(int i=0;i<=2*n+233;i++) f[i]=-1,lt[i]=0,alo[i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read(),y=read();
		add(x,y),eback_add(y,x);
	}
	S=read(),T=read();
	dfs(T);
	lt[T]=1;
	// for(int i=1;i<=n;i++)
	// {
	// 	if(!lt[i]) printf("WoW: %d\n",i);
	// }
	//if(lt[1]) printf("WTW %d\n");
	
	for(int x=1;x<=n;x++)
	{
		bool flag=1;
		if(head[x]==0)
		{
			//printf("SAD :%d\n",x);
			alo[x]=0;
			continue;
		}
		for(int i=head[x];i;i=edge[i].next)
		{
			int yt=edge[i].to;
			if(!lt[yt])
			{
				//if(x==1) printf("wtf: %d\n",yt);
				flag=0;
				break;
			} 
		}
		if(flag) alo[x]=1;
	}
	alo[T]=1;
	// for(int i=1;i<=n;i++)
	// {
	// 	if(alo[i]) printf("YES: %d\n",i);
	// }
	solve(S);
	printf("%d\n",f[S]);
	return 0;
}

用的dfs找最短路

2021/9/22 21:47
加载中...