今天做到一道最短路的题，原题https://loj.ac/problem/10081
题目大意为给一张有n个顶点的图，点与点之间有m1条道路，m2条航线，道路是双向的，且权值非负，而航线是单向的，权值可能为负，保证两点之间如果有航线就不会有道路。现给定起始点s，求s到每个点的最短路径，如果没有则输出“NO PATH”。
我当时看到这题那叫一个高兴啊，以为又是一道水题，因为有负权边，不能用Dijkstra，选择用SPFA。那么有没有负环呢？经过实测数据并没有负环，本以为可以轻松AC了，然而评测结果如下：
最后两个测试点T了。手写队列，读入优化，各种常数优化都用完了，还是超时。现在可以基本确定出数据的人贱贱地卡SPFA了。。。
怎么办呢，又不能用Dijkstra，这时我找到了某某任学长（闻角大仙）。
在某某任学长的帮助下，我了解了一下SPFA的SLF(Small Label First)优化。顾名思义，这种策略就是当要把一个节点入队时，判断它与队头的大小，如果dis[v]<dis[h](v为待入队节点，h为队头)，就把它从队头插入，否则从队尾插入。有点贪心的思想，如果这个点比队头还要小的话，就先用它来松弛其它节点。很明显要用双端队列实现了，部分代码如下：
inline void SPFA(int s)
{
register int p,h,v,w;
fill(dis+1,dis+n+1,INF);
dis[s]=0;
vis[s]=true;
q.push_back(s);
do
{
h=q.front();q.pop_front();
vis[h]=false;
for(p=tail[h];p;p=e[p].last)
{
v=e[p].v;w=e[p].w;
if(dis[v]>dis[h]+w)
{
dis[v]=dis[h]+w;
if(!vis[v])
{
if(dis[v]<dis[q.front()]&&!q.empty（）)//这个判断很重要，如果v点比队头更优，就把它从队头入队
q.push_front(v); //注意双端队列如果在队列为空时从队头入队会出锅的
else q.push_back(v);
vis[v]=true;
}
}
}
}while(!q.empty());
}
提交后测试情况：
快了好几倍啊！
这里我用的手写的双端队列，因为比用STL更快，附上手写代码（这应该是比较简洁可靠的手写双端队列方式了，一看便知不是我写的）：
struct Deque{
LL l, r, q[N];
Deque() {l = 0; r = 0;}
bool empty() {return !(l ^ r);}
void push_back(LL v) {q[r++] = v; r %= N;}
void push_front(LL v) {q[l = (l - 1 + N) % N] = v;}
void pop_front() {++l; l %= N;}
void pop_back() {r = (r - 1 + N) % N;}
LL front() {return q[l];}
};
此外SPFA还有LLL(Large Lable Last)优化，这里就不赘述了（其实是笔者不会），有兴趣的朋友可以去了解一下。
希望能帮到大家，请多多指教.
2018-08-17