前向星+SPFA
我是在做USACO的sweet butter時(shí)偶然發(fā)現(xiàn)這個(gè)東西的。。。
這個(gè)算法，簡單的說就是隊(duì)列優(yōu)化的bellman-ford,利用了每個(gè)點(diǎn)不會(huì)更新次數(shù)太多的特點(diǎn)發(fā)明的此算法（僅為個(gè)人理解=.=）
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。SPFA的實(shí)現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡單：
設(shè)Dist代表S到I點(diǎn)的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點(diǎn)之前的一個(gè)點(diǎn)的編號(hào)。開始時(shí)Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
維護(hù)一個(gè)隊(duì)列，里面存放所有需要進(jìn)行迭代的點(diǎn)。初始時(shí)隊(duì)列中只有一個(gè)點(diǎn)S。用一個(gè)布爾數(shù)組記錄每個(gè)點(diǎn)是否處在隊(duì)列中。
每次迭代，取出隊(duì)頭的點(diǎn)v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長度為len，判斷Dist[v]+len是否小于Dist，若小于則改進(jìn)Dist，將Fa記為v，并且由于S到u的最短距離變小了，有可能u可以改進(jìn)其它的點(diǎn)，所以若u不在隊(duì)列中，就將它放入隊(duì)尾。這樣一直迭代下去直到隊(duì)列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。
SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。設(shè)一個(gè)點(diǎn)用來作為迭代點(diǎn)對(duì)其它點(diǎn)進(jìn)行改進(jìn)的平均次數(shù)為k，有辦法證明對(duì)于通常的情況，k在2左右
前向星優(yōu)化：
不要把前向星想成什么高深莫測(cè)的東西……它其實(shí)就是一種鄰接表的緊縮存儲(chǔ)形式。
為什么叫前向星？因?yàn)樗菍⑦叞凑涨岸它c(diǎn)排序，并用一個(gè)數(shù)組k[i]記錄端點(diǎn)i第一次以左端點(diǎn)出現(xiàn)的位置。這樣，我們就能用O(E)的空間復(fù)雜度存儲(chǔ)下一個(gè)鄰接表，而避免了鏈表或N^2的龐大空間消耗。
當(dāng)然，實(shí)際上我們并不需要排序：因?yàn)槲覀冎恍枰滥骋粭l邊應(yīng)該放到什么位置即可。因而我們還需要一個(gè)數(shù)組t[i]存儲(chǔ)從i出發(fā)的邊的條數(shù)。則需要存儲(chǔ)在的位置就可以很輕易地求得。（詳見代碼）
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.