前向星

前向星是一個邊集數組，把邊的起點終點和權值存起來，然後以起點從小到大或者從大到小排序，記錄每個頂點在數組中的起始位置和長度，以達到節省空間的目的。

一種數據結構，以儲存邊的方式來存儲圖。
構造方法如下：
讀入每條邊的信息
將邊存放在數組中
把數組中的邊按照起點順序排序
前向星就構造完了
通常用在點的數目太多，或兩點之間有多條弧的時候。
一般在別的數據結構不能使用的時候才考慮用前向星。
除了不能直接用起點終點定位以外，前向星幾乎是完美的。
---------------------------------------------------------------------------------------------------------
最基本的前項星最佳化的SPFA(有向圖)，複雜度O(ke).
var
a,b,e:array[1..1000] of longint;
vis:array[1..2000] of boolean;
q,d,f:array[1..2001] of longint;
n,m,i,s,t:longint;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr 1];
repeat
while a&#91;i&#93;<x do inc(i);
while a&#91;j&#93;>x do dec(j);
if not(i>j) then begin
y:=a&#91;i&#93;; a&#91;i&#93;:=a&#91;j&#93;; a&#91;j&#93;:=y;
y:=b&#91;i&#93;; b&#91;i&#93;:=b&#91;j&#93;; b&#91;j&#93;:=y;
y:=e&#91;i&#93;; e&#91;i&#93;:=e&#91;j&#93;; e&#91;j&#93;:=y;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure spfa(s:longint);
var i,k,l,t:longint;
begin
fillchar(vis,sizeof(vis),0);
for i:=1 to n do d&#91;i&#93;:=maxlongint;
d&#91;s&#93;:=0;
l:=0;
t:=1;
q[1]:=s;
vis&#91;s&#93;:=true;
repeat
l:=l mod 10000 +1;
k:=q&#91;l&#93;;
for i:=f&#91;k&#93; to f&#91;k+1&#93;-1 do
if d&#91;k&#93;+e&#91;i&#93;<d&#91;b&#91;i&#93;&#93; then
begin
d&#91;b&#91;i&#93;&#93;:=d&#91;k&#93;+e&#91;i&#93;;
if not vis&#91;b&#91;i&#93;&#93; then begin
t:=t mod 10000 +1;
q&#91;t&#93;:=b&#91;i&#93;;
vis&#91;b&#91;i&#93;&#93;:=true;
end;
end;
vis&#91;k&#93;:=false;
until l=t;
end;
Begin
readln(n,m);
for i:=1 to m do
readln(a&#91;i&#93;,b&#91;i&#93;,e&#91;i&#93;);
qsort(1,m);
for i:=1 to m do
if f&#91;a&#91;i&#93;&#93;=0 then f&#91;a&#91;i&#93;&#93;:=i;
f&#91;n+1&#93;:=m+1;
for i:=n downto 1 do
if f&#91;i&#93;=0 then f&#91;i&#93;:=f&#91;i+1&#93;;
readln(s,t);
spfa(s);
writeln(d&#91;t&#93;);
end.
例如vijos 的P1082 叢林探險 便可以用前向星+SPFA快速解決