SPFA（SLF优化+LLL优化）

最近发现SPFA是可以优化的啊！真的是惊了！废话不多说这里简单讲解一下如何优化SPFA

Small Lable First (SLF)

这个优化就是让我们每一次进行进队操作的时候判断当前的队首点位的距离大小是不是比我们将要塞进去的点的距离大，如果大那么我们从前面塞进去，否则从后面塞进去即可，这里需要改变的就是把容器改变一下，把queue改成deque就可以了。

Large Lable Last(LLL)

这个优化就是让我们每一次进行出队操作的时候进行一次判断，如果当前出队的距离大小比当前队列里所存的距离之和的平均值大的话，我们就暂时不要让当前元素出队，我们就把他从后面压回去，判断下一个队首元素。

注意：

SLF优化的时候一定要判断当前队列是不是空的，如果是空的直接压入就可以了，如果不这样会RE。

下面是一篇加了双优化的SPFA：227ms

/*
    Name: P3371 【模板】单源最短路径（弱化版）
    Copyright: njc
    Author: Mudrobot
    Date: 2018/11/2 9:41:20
    Description: Spfa
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define LL long long
#define N 1000003
#define INF 2147483647
using namespace std;
/*inline char gc() {
  static char buf[1<<18],*fs,*ft;
  return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
  register T k=0,f=1;
  register char c=gc();
  for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
  for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
  aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
    int next,to,val;
}edge[N];
bool vis[N];
int qnt,n,m,s,sum,dis[N],head[N],size=0;
inline void add(int a,int b,int c){
    edge[++qnt].next=head[a];edge[qnt].to=b;edge[qnt].val=c;head[a]=qnt;
}
inline void spfa(){
    deque<int> q;
    for(register int i=1;i<=n;++i) dis[i]=INF;
    dis[s]=0;vis[s]=true;q.push_back(s);sum=0;size=1;
    while(!q.empty()){
        int u=q.front();q.pop_front();//Large Lable Last
        if(dis[u]*size>sum){
            q.push_back(u);
            continue;
        }
        //int u=q.front();q.pop_front();
        vis[u]=false;sum-=dis[u];size--;
        for(register int i=head[u];i;i=edge[i].next){
            int v=edge[i].to,val=edge[i].val;
            if(dis[v]>dis[u]+val){
                dis[v]=dis[u]+val;
                if(!vis[v]){
                    size++;
                    sum+=dis[v];
                    vis[v]=true;
                    if(q.empty()) q.push_back(v);//Small Lable First
                    else{
                        int judge=dis[q.front()];
                        if(dis[v]>judge) q.push_back(v);
                        else q.push_front(v);
                    }
                }
            }
        }
    }
}
int main()
{
    //freopen(".in", "r", stdin);freopen(".out", "w", stdout);
    read(n);read(m);read(s);int a,b,c;
    for(register int i=1;i<=m;++i){
        read(a);read(b);read(c);
        add(a,b,c);
    }
    spfa();
    for(register int i=1;i<=n;++i) out(dis[i]),putchar(' ');//printf("%d ",dis[i]);
    //fclose(stdin);fclose(stdout);
    return 0;
}
/*
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
*/

不加优化的444ms

优化效果还是非常明显的！