记搜+dijk只有30分wa求助
查看原帖
记搜+dijk只有30分wa求助
378346
expnoi楼主2022/8/1 17:16
#include<bits/stdc++.h>
using namespace std;
int vis[10010],v[10010],g[10010],head[1000010],n,m,d,y,eid=1,s,t,p[100010],in[100010],out[100010],dis[100010];
struct node{
	int v,next;
}e[1000010];
inline void insert(int u,int v)
{
	e[eid].v=v;
	e[eid].next=head[u];
	head[u]=eid++;
}
inline bool dfs(int x)
{
	if(x==t)
	{
		v[x]=1;
		return 1;
	}
	int flg=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].v;
		if(vis[y])continue;
		if(g[y])//先前已经被访问过
		{
			if(v[y])
			{
				flg=1;
			}
			continue;
		}
		vis[y]=1;
		flg|=dfs(y);
		vis[y]=0;
	}
	g[x]=1;
	return v[x]=flg;
}
int main()
{
	cin>>n>>m;
	int S=0; 
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		insert(u,v);
		out[u]++;
	}
	cin>>s>>t;
	dfs(s);
	for(int x=1;x<=n;x++)
	{
		int cnt=0;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].v;
			if(v[y])
			{
				cnt++;
			}
			/*if(x==13&&!v[y])
			{
				cout<<y<<"\n";
			}*/
		}
		if(cnt==out[x]&&out[x])
		{
			p[x]=1;
		}
		/*if(x==13)
		{
			cout<<x<<" "<<out[x]<<" "<<cnt<<"\n";
		}*/
	}
	p[t]=1;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	for(int k=1;k<n;k++)
	{
		int minn=0x7fffffff,u;
		for(int i=1;i<=n;i++)
		{
			if(minn>dis[i]&&!vis[i])
			{
				u=i;
				minn=dis[i];
			}
		}
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].v;
			if(!p[v])continue;
			dis[v]=min(dis[v],dis[u]+1);
		}
	}
	if(dis[t]!=0x3f3f3f3f)
	cout<<dis[t];
	else
	{
		puts("-1");
	}
}
2022/8/1 17:16
加载中...