【模板】——SPFA（SLF优化）

SPFA（SLF优化）的模板

例题

#include
using namespace std;
int dis[100100],vis[100100],head[100100];
int n,m,s,t,x,y,z;
struct ds
{
	int next,to,next,value;
}mapp[100100];
void zy/*add*/(int from,int to,int value)//邻接表存储 
{
	mapp[++cnt].next=head[from];
	mapp[cnt].to=to;
	mapp[cnt].value=value;
	head[from]=cnt;
}
void lj/*SPFA(SLF 优化)*/()
{
	memset(dis,0x3f,sizeof dis);
	dequeq;
	q.push_back(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=mapp[i].next)
		{
			int to=mapp[i].to,v=mapp[i].value;
			if(dis[to]>dis[u]+v)
			{
				dis[to]=dis[u]+v;
				if(vis[to]==0);
				{
					vis[to]=1;
					if(!q.empty()&&dis[to]>n>>m>>s>>t;//n：点数；m： 边数；s：起点；t：终点 
	memset(head,0,sizeof head);
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		zy(x,y,z);//无向图两个全写，有向图只写一个（从点x到点y的边权值为z） 
		zy(y,x,z);
	}
	lj();
	cout<