首先先明确一个问题，SPFA是什么？（不会看什么看，一边学去，），SPFA是bellman-ford的队列优化版本，只有在国内才流行SPFA这个名字，大多数人就只知道SPFA就是一个顶尖的高效算法，却不知道还能继续优化，这个优化虽然也没有你想的那么麻烦，只不过多了几个判断语句罢了，5分钟就能学会，但是这也得运用到分类讨论，其实SPFA有三种优化方法，效果并不是很明显。
这三个测试点通过情况所对应的分别是SPFA的三种优化方法，这个时间也是因题而异，像这道题，效果并不好，但是看别人写的博客，他们提交了一道数据对于优化后的SPFA比较有利，测试时间差距能看出来，但是效果也就是减少十几毫秒而已，但是也是有的，万一题目会卡这十几毫秒呢？
1. SLF优化
还记得吗？在我们学SPFA的时候，要把每一个入队的点插入到队尾，可是有些时候这个点作为队尾没有作为队头效率高，因为这个点有时放在队首就能直接用，那么什么样的点作为队首更好呢？当然是dis值越小越可能刷新其它dis值，所以对比当前元素与对首元素的dis值，如果当前元素的dis值更小，那么把当前元素插入到队首，否则插入到队尾。如果你不是很了解队列，或者还是现学的，一定会纳闷，不就能q.push( );吗？哪来的队首呢？此时queue<int>q;应该改为deque<int>q;双端队列，就有q.push_front( );和q.push_back( );了。
代码如下（红色处为优化对应的新增代码）：
1 void SPFA() 2 { 3 memset(dis,inf,sizeof(dis)); 4 deque q; 5 q.push_back(1);dis[1]=0;vis[1]=1; 6 while(q.size()) 7 { 8 x=q.front();q.pop_front();vis[x]=0; 9 for(int i=head[x];i;i=map[i].next)10 {11 s=map[i].to;12 if(dis[s]>dis[x]+map[i].value)13 {14 dis[s]=dis[x]+map[i].value;15 if(vis[s]==0)16 {17 if(dis[s] 2. LLL优化
如果懂了上一个SLF优化，那么这个LLL优化就很好理解了，SLF表示小的优先，LLL表示大的最后，那么什么样的的dis值是大的呢？难道还和队首元素比较吗？当然不是，是于队列的平均数来比较，如果大于这个平均数就放到最后。
代码如下（红色处为优化对应的新增代码）：
1 void SPFA() 2 { 3 memset(dis,inf,sizeof(dis)); 4 queue q; 5 q.push(1);dis[1]=0;vis[1]=1; 6 while(q.size()) 7 { 8 p=q.front();q.pop(); 9 if(dis[p]*cnt_2>sum)10 {11 q.push(p);12 continue;13 }14 sum-=dis[p];cnt_2--;15 vis[p]=0;16 for(int i=head[p];i;i=map[i].next)17 {18 s=map[i].to;19 if(dis[s]>dis[p]+map[i].value)20 {21 dis[s]=dis[p]+map[i].value;22 if(vis[s]==0)23 {24 vis[s]==1;25 q.push(s); 26 cnt_2++;27 sum+=dis[s];28 }29 }30 }31 }32 } 2. SLF+LLL优化
这个就很简单直接了，把两个新增代码搓一块了就行。
代码如下（红色处为优化对应的新增代码）：
1 void SPFA() 2 { 3 memset(dis,inf,sizeof(dis)); 4 deque q; 5 q.push_back(1);dis[1]=0;vis[1]=1; 6 while(q.size()) 7 { 8 p=q.front();q.pop_front(); 9 if(dis[p]*cnt_2>sum)10 {11 q.push_back(p);12 continue;13 }14 sum-=dis[p];cnt_2--;15 vis[p]=0;;16 for(int i=head[p];i;i=map[i].next)17 {18 s=map[i].to;19 if(dis[s]>dis[p]+map[i].value)20 {21 dis[s]=dis[p]+map[i].value;22 if(vis[s]==0)23 {24 vis[s]==1;25 if(dis[s] 怎么样，你学会了吗？