算法适用场景：非负权，负权非负环。

算法的实现在贝尔曼福特算法的基础上适用队列优化（类似于广度优先搜索的方法）将修改后的点放入队列后设置标记，防止下一次再利用该点进行松弛，直到改点被使用后为止。

需要用到的空间：vector领接表，队列（存放点），dis[]单源最短路径，sign[]标记是否入列过，neg[]用来判断负环（无法在负环情况下结果问题）

代码模板：

void spfa(ll s)
{
	ll dis[10010];
	bool sign[10010];
	ll neg[10010];
	//初始化 
	memset(neg,0,sizeof neg);
	neg[s]=1;
	for(ll i=1;i<=n;i++)
	{
		dis[i]=INF; sign[i]=false;
	}
	dis[s]=0;
	//队列操作 
	queue<ll> q;
	q.push(s);
	sign[s]=true;
	ll cnt=0;
	while(!q.empty())
	{
		ll u = q.front();
		q.pop();
		sign[u]=false;
		for(ll i=0;i<e[u].size();i++)
		{
			ll v = e[u][i].v,w = e[u][i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
		//		pre[v]=u;
				if(!sign[v])
				{
					sign[v]=true;
					q.push(v);
					neg[v]++;
					if(neg[v]>n)//出现负圈 
						return;
				}
			}
		}
	}
	cout<<dis[n]<<endl;
	//有些程序需要打印路径，这个以后再说 
}

void find(int a)//利用递归找回路径 
{
	if(a==S)
	{
		cout << S;
		return;
	}
	else{
		find(father[a]);
	}
	cout << " " <<a;
}