关于SPFA的优化

SPFA两个著名优化（SLF和LLL）：

SPFA 是按照 FIFO 的原则更新距离的, 没有考虑到距离标号的作用。

实现中 SPFA 有两个非常著名的优化: SLF 和 LLL。

SLF: Small Label First 策略. （比较常用）
实现方法：设队首元素为 $i$ , 队列中要加入节点 $j$ , 在 $d_j \le d_i$ 时加到队首而不是队尾, 否则和普通的 SPFA 一样加到队尾.

LLL: Large Label Last 策略. （不太常用）

设队列 Q 中的队首元素为 i，距离标号的平均值为 $\overline d = \frac {\sum_{j \in Q} d_j }{\left| Q \right|}$ ，每次出队时，若 $d_i > \overline d$ ，把 i 移到队列末尾，如此反复，直到找到一个 $i$ 使 $d_i \le \overline d$ ，将其出队。

话说某次在群里问过关于SLF优化的实现问题，木人理我。。。。

网上这方面的资料貌似也不多。。。。

这两天看到了双端队列，然后就突然想起了SLF优化。。自己实现了下，大牛请无视。

以POJ 3259为例，上面的是优化后的，下面的是不加优化的。不加优化的SPFA 跑了157MS，加了SLF优化后跑了94MS。可以看出，使用SLF优化可以节约一部分的时间。

SLF代码实现(POJ 3259)：

1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <deque>
  6 using namespace std;
  7 const int N=501;
  8 const int NN=100001;
  9 const int inf=0x7fffffff;
10 int n,nu;
11 typedef struct node
12 {
13     int adj,val;
14     struct node *next;
15 };
16 node node[NN],*p[N];
17 int SPFA()
18 {
19     deque<int> qu;
20     int x,i,a,b;
21     int vis[N],dis[N],num[N];
22     struct node *head[N];
23     for(i=1;i<=n;i++)
24     {
25         vis[i]=0;
26         num[i]=0;
27         dis[i]=inf;
28         head[i]=p[i];
29     }
30     dis[1]=0;
31     vis[1]=1;
32     num[1]++;
33     qu.push_back(1);
34     while(!qu.empty())
35     {
36         x=qu.front();
37         qu.pop_front();
38         vis[x]=0;
39         head[x]=p[x];
40         while(head[x])
41         {
42             a=head[x]->adj;
43             b=head[x]->val;
44             if(dis[a]>dis[x]+b)
45             {
46                 dis[a]=dis[x]+b;
47                 if(!vis[a])
48                 {
49                     vis[a]=1;
50                     num[a]++;
51                     if(num[a]>=n)
52                         return 1;
53                     if(!qu.empty())
54                     {
55                         if(dis[a]>dis[qu.front()])
56                             qu.push_back(a);
57                         else
58                             qu.push_front(a);
59                     }
60                     else
61                         qu.push_back(a);
62                 }
63             }
64             head[x]=head[x]->next;
65         }
66     }
67     return 0;
68 }
69 int main()
70 {
71     int t,i,m,w,a,b,c;
72     scanf("%d",&t);
73     while(t--)
74     {
75         memset(node,0,sizeof(node));
76         memset(p,0,sizeof(p));
77         nu=0;
78         scanf("%d%d%d",&n,&m,&w);
79         for(i=0;i<m;i++)
80         {
81             scanf("%d%d%d",&a,&b,&c);
82             node[nu].adj=b;
83             node[nu].val=c;
84             node[nu].next=p[a];
85             p[a]=&node[nu];
86             nu++;
87             node[nu].adj=a;
88             node[nu].val=c;
89             node[nu].next=p[b];
90             p[b]=&node[nu];
91             nu++;
92         }
93         for(i=0;i<w;i++)
94         {
95             scanf("%d%d%d",&a,&b,&c);
96             node[nu].adj=b;
97             node[nu].val=-c;
98             node[nu].next=p[a];
99             p[a]=&node[nu];
100             nu++;
101         }
102         if(SPFA())
103             puts("YES");
104         else
105             puts("NO");
106     }
107     return 0;
108 }