一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息将边存放在数组中把数组中的边按照起点顺序排序前向星就构造完了通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。

最基本的前项星优化的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快速解决