10分代码,9个点MLE,蒟蒻求调
查看原帖
10分代码,9个点MLE,蒟蒻求调
327295
GalwayGirl楼主2022/7/6 12:49
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,head[11000][3],c[3],s,t,flag[11000],zs[11000],dis[11000];
struct xzh
{
	int next,to,w;
}edge[210000][2];
void add(int u,int v,int biao,int w)
{
	c[biao]++;
	edge[c[biao]][biao].next=head[u][biao];
	edge[c[biao]][biao].to=v;
	edge[c[biao]][biao].w=w;
	head[u][biao]=c[biao];
}
void spfa(int biao,int now)
{
	if(biao==1)
	{
		flag[now]=1;
		for(int i=head[now][biao];i;i=edge[i][biao].next)spfa(biao,edge[i][biao].to);
	}
	else
	{
		queue<int>q;
		flag[now]=1;
		dis[now]=0;
		q.push(now);
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			flag[u]=0;
			for(int i=head[u][biao];i;i=edge[i][biao].next)
			{
				int v=edge[i][biao].to;
				if(dis[u]+edge[i][biao].w<dis[v]&&!zs[v])
				{
					dis[v]=dis[u]+edge[i][biao].w;
					if(!flag[v])
					{
						flag[v]=1;
						q.push(v);
					}
				}
			}
		}
	}
}
void js(int now,int biao)
{
	zs[now]=1;
	for(int i=head[now][biao];i;i=edge[i][biao].next)zs[edge[i][biao].to]=1;
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		cin>>u>>v;
		add(v,u,1,1);
		add(u,v,2,1);
	}
	cin>>s>>t;
	spfa(1,t);
	for(int i=1;i<=n;i++)if(!flag[i])js(i,1);
	if(zs[s]==1)
	{
		cout<<-1;
		return 0;
	}
	memset(flag,0,sizeof(flag));
	memset(dis,0x7f,sizeof(dis));
	spfa(2,s);
	cout<<dis[t];
	return 0;
}
2022/7/6 12:49
加载中...