pascal 最短路DJ算法的优化,要NlogN的

来源:百度知道 编辑:UC知道 时间:2024/06/25 22:16:16
如题

又是个不明题意的ls。。
看看我的吧。。楼主想要的应该是用堆维护的dijkstra算法,这个算法的时间复杂度是NlogN的,程序如下:
const
maxn=100;
type
link=^node; //邻接表类型
node=record
v,w :integer;
next :link;
end;
htype=record //堆节点
v,d,p :integer;
end;
var
n,s,hl :integer; //顶点数;源点;堆长度
heap :array[0..maxn]of htype;
hpos :array[1..maxn]of integer; //hpos[v]:顶点v在堆中的位置
g :array[1..maxn]of link; //邻接表
procedure insert(u,v,w:integer); //将权值为w的边(u,v)插入到邻接表
var
x :link;
begin
new(x);
x^.v:=v; x^.w:=w;
x^.next:=g[u]; g[u]:=x;
end;
procedure init; //初始化
var
u,v,w :integer;
begin
assign(input,'g.in');reset(input);
readln(n,s);
while not eof do
begin
readln(u,v,w);
insert(u,v,w