这里介绍怎么求k短路
A*搜索 估价函数f[i]=g[i]+h[i];
在这里g[i]表示到达点i当前路径长，h[i]表示点i到达终点的最短距离
在搜索中，每次都取队列估价函数值最小的点，然后把它所能到达的点更新进入队列
显然这需要一个优先队列来维护（heap）
当终点第k次出队时，当前路径长度就是k短路
const max=;
type link=^node;
node=record
po,len:longint;
next:link;
end;
point=record
data,num:longint;
end;
var w,ow:array[..] of link;
v:array[..] of boolean;
d:array[..] of longint;
heap:array[..] of point; //堆维护估价函数值
st,en,i,n,m,j,t,k,x,y,z,s:longint;
p:link; procedure sift(x:longint); //堆的下沉
var i,j:longint;
begin
i:=x;
j:=i*;
while j<=t do
begin
if (j+<=t) and (heap[j].data>heap[j+].data) then inc(j);
if heap[i].data>heap[j].data then
begin
swap(heap[i],heap[j]);
i:=j;
j:=i*;
end
else exit;
end;
end; procedure up(x:longint); //堆的上浮
var i,j:longint;
begin
i:=x;
j:=i div ;
while j> do
begin
if heap[i].data<heap[j].data then
begin
swap(heap[i],heap[j]);
i:=j;
j:=i div ;
end
else exit;
end;
end; procedure add(x,y:longint;var q:link);
var p:link;
begin
new(p);
p^.po:=y;
p^.len:=z;
p^.next:=q;
q:=p;
end; procedure dij; //求点到终点的距离
var p:link;
begin
fillchar(v,sizeof(v),false);
v[en]:=true;
for i:= to n do
d[i]:=max;
d[en]:=;
p:=ow[en];
while p<>nil do
begin
d[p^.po]:=min(d[p^.po],p^.len); //用邻接表重要的细节
p:=p^.next;
end;
for i:= to n- do
begin
x:=max;
y:=;
for j:= to n do
if not v[j] and (d[j]<x) then
begin
x:=d[j];
y:=j;
end;
if x=max then exit;
v[y]:=true;
p:=ow[y];
while p<>nil do
begin
d[p^.po]:=min(d[p^.po],p^.len+x);
p:=p^.next;
end;
end;
end; function astar(st,ed:longint):longint;
var p:link;
begin
heap[].data:=d[st];
heap[].num:=st;
t:=;
s:=;
astar:=-;
while t<> do
begin
x:=heap[].num; //退队
y:=heap[].data-d[x];
swap(heap[],heap[t]);
dec(t);
sift();
if x=en then
begin
s:=s+;
if s=k then exit(y);
end;
p:=w[x];
while p<>nil do //更新所有能到达的点入队
begin
inc(t);
heap[t].num:=p^.po;
heap[t].data:=y+p^.len+d[p^.po];
up(t);
p:=p^.next;
end;
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(x,y,z);
add(x,y,w[x]);
add(y,x,ow[y]); //注意有向需反向建边，快速求点到终点的距离
end;
readln(st,en,k);
if st=en then inc(k); //注意终点与起点重合时，路径为0的不算
dij;
writeln(astar(st,en));
end.
而对于poj3255，求无向图的次短路也可以用A*，在n<=5000时还是可以过的，注意那时候就不需要反向建边了
k短路算法还是很好理解的