【学习笔记】spfa

一、spfa

模板：

void spfa(int x)
{
	for(int i=1;i<=n;i++)
		vis[i]=0,dis[i]=inf;
	dis[1]=0,f[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(int i=first[t];i;i=e[i].next)
		{
			int to=e[i].to;
			if(dis[t]+e[i].v<dis[to])
			{
				f[to]=f[t]+1;
				if(f[to]>n)
				{
					cout<<"Yes";//存在负环
					exit(0);
				}
				dis[to]=dis[t]+e[i].v;
				if(vis[to]==0)
				{
					q.push(to);
					vis[to]=1;
				}
			}
		}
	}
}