关于SPFA，他死了（懂的都懂）
一般来说，我们有两种优化方法。
SLF优化：
SLF优化，即 Small Label First 策略，使用 双端队列 进行优化。
一般可以优化15%~20%，在竞赛中比较常用。
设从 u 扩展出了 v ，队列中队首元素为 k ，若 dis[ v ] < dis[ k ] ，则将 v 插入队首，否则插入队尾。
注：队列为空时直接插入队尾。
1 deque<int> q;
2
3 inline void spfa(int x)
4 {
5 memset(d,0x3f,sizeof(d));
6 memset(v,0,sizeof(v));
7 d[x]=0;v[x]=1;
8 q.push_back(x);
9 while(q.size())
10 {
11 int index=q.front();q.pop_front();
12 v[index]=0;
13 for(int i=head[index];i;i=g[i].next){
14 int y=g[i].ver,z=g[i].edge;
15 if(d[y]>d[index]+z){
16 d[y]=d[index]+z;
17 if(!v[y]){
18 if(!q.empty()&&d[y]>=d[q.front()]) q.push_back(y);
19 else q.push_front(y);
20 v[y]=1;
21 }
22 }
23 }
24 }
25 }
LLL优化：
LLL优化，即 Large Label Last 策略，使用 双端队列 进行优化。
一般用SLF+LLL可以优化50%左右，但是在竞赛中并不常用LLL优化。（所以我就懒得写了，这是从这个大佬那里嫖来的）
设队首元素为 k ，每次松弛时进行判断，队列中所有 dis 值的平均值为 x 。
若 dist[ k ] > x ，则将 k 插入到队尾，查找下一元素，直到找到某一个 k 使得 dis[ k ] <= x ，则将 k 出队进行松弛操作。
1 void spfa(){ 2 int u,v,num=0; 3 long long x=0; 4 list<int> q; 5 for(int i=1;i<=n;i++){path[i]=MAX;vis[i]=false;} 6 path[s]=0; 7 vis[s]=true; 8 q.push_back(s); 9 num++; 10 while(!q.empty()){ 11 u=q.front(); 12 q.pop_front(); 13 num--;x-=path[u]; 14 while(num&&path[u]>x/num){ 15 q.push_back(u); 16 u=q.front(); 17 q.pop_front(); 18 } 19 vis[u]=false; 20 for(int i=head[u];i;i=a[i].next){ 21 v=a[i].to; 22 if(relax(u,v,a[i].w)&&!vis[v]){ 23 vis[v]=true; 24 if(!q.empty()&&path[v]<path[q.front()])q.push_front(v); 25 else q.push_back(v); 26 num++;x+=path[v]; 27 } 28 } 29 } 30 for(int i=1;i<=n;i++)printf("%d ",path[i]); 31 printf("\n"); 32 }
原文：https://www.cnblogs.com/DarkValkyrie/p/11025087.html