SPFA75分求助(队列写法但是TLE了5个点)
查看原帖
SPFA75分求助(队列写法但是TLE了5个点)
463210
zzzYheng楼主2021/7/4 15:49
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e3+10;
int read()
{
	int sum=0,flag=1; char ch=getchar();
	for(;(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
	if(ch=='-') flag=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return flag*sum;
}
int n,m;
int edge[MAXN*2][3],head[MAXN],len;
int dis[MAXN],vis[MAXN],times[MAXN];
queue<int> q;
int add(int x,int y,int z)
{
	len++;
	edge[len][0]=x;
	edge[len][1]=head[y];
	edge[len][2]=z;
	head[y]=len;
}
int spfa(int begin)
{
	int i,j;
	memset(dis,-0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[begin]=0;
	vis[begin]=1;
	q.push(begin);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		vis[x]=0;
		for(i=head[x];i;i=edge[i][1])
		{
			int y=edge[i][0];
			if(dis[y]<dis[x]+edge[i][2])
			{	
				if(++times[y]>n) return 0;
				dis[y]=dis[x]+edge[i][2];
				if(vis[y]==0)
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return 1;
}
int main()
{
	int i,j;
	n=read(),m=read();
	for(i=1;i<=m;i++)
	{
		int x,a,b,c;
		x=read();
		if(x==1)
		{
			a=read(),b=read(),c=read();
			add(a,b,c);
		}
		else if(x==2)
		{
			a=read(),b=read(),c=read();
			add(b,a,-c);
		}
		else
		{
			a=read(),b=read();
			add(a,b,0);
			add(b,a,0);
		}
	}
	for(i=1;i<=n;i++)
		add(i,0,0);
	if(spfa(0)==1) printf("Yes");
	else printf("No");
	return 0;
} 
2021/7/4 15:49
加载中...