SPFA？？SPFA已经死了，完结撒花

前置知识：Bellman−Ford算法

一、注意松弛：dis[v]=min⁡⁡(dis[v],dis[u]+dis(u,v))
二、判断负权边：进行n−1次松弛后再来一次松弛，如果答案还有变化，说明有负权边。

核心代码：

    for (int k=1;k<=n-1;k++)//n是顶点的数量
        for (int i=1;i<=m;i++)//m是边的数量
            if (dis[v[i]]>dis[u[i]]+w[i])//u[i]和v[i]是边的两个顶点
                dis[v[i]]=dis[u[i]]+w[i];//w[i]是边的费用

分析：首先，程序运行n-1次的原因是：在n个顶点的图中，任意两点的最短路最多包含n−1条边；从而可计算出时间复杂度为O(nm)。可以发现，我们常常在n−1次循环完成之前就已松弛完毕。因此，若某次松弛没有发生变化，即为判定跳出循环标志。

SPFA算法：基础版

首先，对队首顶点u的所有出边松弛。
其中，若有一条u→v的边可以使源点到v的距离变短，便将v加入队尾。
同时想到，同一顶点在队列中多次出现没有意义，因此可开一数组判重；
顶点u的所有出边松弛完毕后，使u出队，直到队列为空。
（是不是很像bfs？？）

#include <bits/stdc++.h>
using namespace std;

const int inf=2147483647;
const int maxn=10005;
int n,m,b,e=0,i,j;
int dis[maxn],head[500005];
bool vis[maxn];
struct node
{
  int next,to,dis;
}edge[500005];

queue<int> q;
void addedge(int from,int to,int dis)
{
    edge[++e].next=head[from];
    edge[e].dis=dis;
    edge[e].to=to;
    head[from]=e;
}

void spfa()
{
    for(i=1;i<=n;i++) dis[i]=inf;
    dis[b]=0;
    q.push(b),vis[b]=1;
    while(!q.empty())
    {
        int begin=q.front();
        q.pop(); 
        for(i=head[begin];i;i=edge[i].next)
        {
            if(dis[edge[i].to]>dis[begin]+edge[i].dis)
            {
                dis[edge[i].to]=dis[begin]+edge[i].dis;
                if(!vis[edge[i].to]) 
                {
                    vis[edge[i].to]=1;
                    q.push(edge[i].to);
                }
            }
        }
        vis[begin]=0;
    }
}
int main()
{
    cin>>n>>m>>b;
    for(int i=1; i<=m; i++)
    {
        int f,t,d;
        cin>>f>>t>>d; 
        addedge(f,t,d); 
    }
    spfa(); 
    for(int i=1; i<=n; i++)
        if(b==i) cout<<0<<' '; 
        else cout<<dis[i]<<' ';
    return 0;
}

然而，众所周知，SPFA是会被毒瘤出题人卡的。
所以如果没有负权边的话，最好还是用Dijkstra（复杂度O((M+N)logN)）。
因此，我们需要对SPFA算法做一些优化。

SPFA算法：LLL优化

LLL优化，即Large Label Last策略，使用双端队列进行优化。
一般用SLF+LLL可以优化50%左右，但是在竞赛中并不常用LLL优化。（所以我就懒得写了，这是从这个大佬那里嫖来的）
设队首元素为 k ，每次松弛时进行判断，队列中所有 dis 值的平均值为 x 。
若 dist[k]>x，则将k插入到队尾，查找下一元素，直到找到某一个k使得dis[k]<=x，则将k出队进行松弛操作。

void spfa()
{
    int u,v,num=0;
    long long x=0;
    list<int> q;
    for(int i=1;i<=n;i++)
    {
        path[i]=MAX;vis[i]=false;
    }
    path[s]=0;
    vis[s]=true;
    q.push_back(s);
    num++;
    while(!q.empty())
    {
        u=q.front();
        q.pop_front();
        num--;x-=path[u];
        while(num&&path[u]>x/num)
        {
            q.push_back(u);
            u=q.front();
            q.pop_front();
        }
        vis[u]=false;
        for(int i=head[u];i;i=a[i].next)
        {
            v=a[i].to;
            if(relax(u,v,a[i].w)&&!vis[v])
            {
                vis[v]=true;
                if(!q.empty()&&path[v]<path[q.front()])q.push_front(v);
                else q.push_back(v);
                num++;x+=path[v];
            }
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",path[i]);
    printf("\n");
}

SPFA算法：SLF优化

SLF优化，即Small Label First策略，使用双端队列进行优化。
一般可以优化15%~20%，在竞赛中比较常用。
设从u扩展出了v,队列中队首元素为k,若dis[v]<dis[k],则将v插入队首，否则插入队尾。

注：队列为空时直接插入队尾。

deque<int> q;

inline void spfa(int x)
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[x]=0;v[x]=1;
    q.push_back(x);
    while(q.size())
    {
        int index=q.front();q.pop_front();
        v[index]=0;
        for(int i=head[index];i;i=g[i].next)
        {
            int y=g[i].ver,z=g[i].edge;
            if(d[y]>d[index]+z)
            {
                d[y]=d[index]+z;
                if(!v[y])
                {
                    if(!q.empty()&&d[y]>=d[q.front()]) q.push_back(y);
                    else q.push_front(y);
                    v[y]=1;
                }
            }
        }
    }
}

基于BFS的SPFA优化

上文提到，原始SPFA在形式上和BFS非常类似。
不同的是，在bfs中，一个点出了队列，就不可能重新进入队列；
但是在SPFA中，一个点可能在出队列之后，再次被放入队列，
即，一个点改进过其它的点之后，过了一段时间可能本身被改进(重新入队)，
并被重复利用以改进其它的点，如此反复迭代下去，直至队列为空。

因此想到，可基于BFS优化SPFA——即，直接从新节点开始往下递归。
判断负环也更为简单：若存在a1​⇒a2​⇒a3​⇒....⇒ak​⇒a1​即可判环，
再用一个数组来记录结点是否在递归栈中即可。

    Void SPFA(Node)
    {
        Instack[Node]=true;
        For (Node,v) ∈ E
            If dis[Node]+edge(Node,v)<dis[v] then
            {
                dis[v]=dis[Node]+edge(Node,v);
                If not Instack[v] then
                    SPFA();
                Else
                    Return;
            }
        Instack[Node]=false;
    }

基于DFS的SPFA相关优化

咕咕咕.....(等待更新)