前向星+SPFA
我是在做USACO的sweet butter時偶然發(fā)現(xiàn)這個東西的。。。
這個算法，簡單的說就是隊列優(yōu)化的bellman-ford,利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法（僅為個人理解=.=）
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點到其他所有點的最短路徑，可以處理負(fù)邊。SPFA的實現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡單：
設(shè)Dist代表S到I點的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
維護一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數(shù)組記錄每個點是否處在隊列中。
每次迭代，取出隊頭的點v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長度為len，判斷Dist[v]+len是否小于Dist，若小于則改進Dist，將Fa記為v，并且由于S到u的最短距離變小了，有可能u可以改進其它的點，所以若u不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。
SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的情況，k在2左右
前向星優(yōu)化：
不要把前向星想成什么高深莫測的東西……它其實就是一種鄰接表的緊縮存儲形式。
為什么叫前向星？因為它是將邊按照前端點排序，并用一個數(shù)組k[i]記錄端點i第一次以左端點出現(xiàn)的位置。這樣，我們就能用O(E)的空間復(fù)雜度存儲下一個鄰接表，而避免了鏈表或N^2的龐大空間消耗。
當(dāng)然，實際上我們并不需要排序：因為我們只需要知道某一條邊應(yīng)該放到什么位置即可。因而我們還需要一個數(shù)組t[i]存儲從i出發(fā)的邊的條數(shù)。則需要存儲在的位置就可以很輕易地求得。（詳見代碼）
Butter題目代碼如下：
Program butter(input,output);
Type
edge=record
x,y,d:longint;
end;
Var
min,res,n,p,c,x,y,i,j,l,r:longint;
te,e:array[0..3000] of edge;
tk,t,k,num,d:array[1..800] of longint;
q:array[1..100000] of longint;
use:array[1..800] of boolean;
Procedure swap(var n1,n2:longint);
Var
tmp:longint;
Begin
tmp:=n1;n1:=n2;n2:=tmp;
End;
Begin
assign(input,'butter.in');reset(input);
readln(n,p,c);
for i:=1 to n do
begin
read(x);
inc(num[x]);
end;
for i:=1 to c do
begin
with e[i*2-1] do readln(x,y,d);
e[i*2]:=e[i*2-1];
swap(e[i*2].x,e[i*2].y);
end;
c:=c*2;
for i:=1 to c do inc(t[e[i].x]);
j:=0;k[1]:=1;
for i:=2 to p do
k[i]:=k[i-1]+t[i-1];
tk:=k;te:=e;
for i:=1 to c do
begin
e[tk[te[i].x]]:=te[i];
inc(tk[te[i].x]);
end;
min:=maxlongint;
for i:=1 to p do
begin
fillchar(q,sizeof(q),0);
fillchar(d,sizeof(d),127);
fillchar(use,sizeof(use),false);
q[1]:=i;l:=1;r:=1;d[i]:=0;use[i]:=true;
repeat
for j:=k[q[l]] to k[q[l]]+t[q[l]]-1 do
if d[q[l]]+e[j].d<d[e[j].y] then
begin
d[e[j].y]:=d[q[l]]+e[j].d;
if not use[e[j].y] then
begin
use[e[j].y]:=true;
inc(r);
q[r]:=e[j].y;
end;
end;
use[q[l]]:=false;
inc(l);
until l>r;
res:=0;
for j:=1 to p do
res:=res+d[j]*num[j];
if res<min then min:=res;
end;
assign(output,'butter.out');rewrite(output);
writeln(min);close(output);
End.