前向星
一种数据结构，以储存边的方式来存储图。
构造方法如下：
读入每条边的信息
将边存放在数组中
把数组中的边按照起点顺序排序
前向星就构造完了
通常用在点的数目太多，或两点之间有多条弧的时候。
一般在别的数据结构不能使用的时候才考虑用前向星。
除了不能直接用起点终点定位以外，前向星几乎是完美的。
---------------------------------------------------------------------------------------------------------
最基本的前项星优化的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[i]<x do inc(i);
while a[j]>x do dec(j);
if not(i>j) then begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=b[i]; b[i]:=b[j]; b[j]:=y;
y:=e[i]; e[i]:=e[j]; e[j]:=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[i]:=maxlongint;
d[s]:=0;
l:=0;
t:=1;
q[1]:=s;
vis[s]:=true;
repeat
l:=l mod 10000 +1;
k:=q[l];
for i:=f[k] to f[k+1]-1 do
if d[k]+e[i]<d[b[i]] then
begin
d[b[i]]:=d[k]+e[i];
if not vis[b[i]] then begin
t:=t mod 10000 +1;
q[t]:=b[i];
vis[b[i]]:=true;
end;
end;
vis[k]:=false;
until l=t;
end;
Begin
readln(n,m);
for i:=1 to m do
readln(a[i],b[i],e[i]);
qsort(1,m);
for i:=1 to m do
if f[a[i]]=0 then f[a[i]]:=i;
f[n+1]:=m+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
readln(s,t);
spfa(s);
writeln(d[t]);
end.
例如Vijos 的P1082 丛林探险 便可以用前向星+SPFA快速解决