注意Extract min过程内要p[h[1].n]=1.(事实上每次移动都需要修改位置数组)
那个所谓的
"[ 讨论 ] 本题卡的是链表懂不!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1月前 / 0 回复 / 0 顶"
知道链表怎么写才是对的么?
While rp+1>rp do rp:=rp+1;
program Heap_Dikstra;
type pnode=^tnode;
tnode=record
n,w:longint;
next:pnode;
end;
hnode=record
n,d:longint;
end;
const maxn=30079;
var g:array[1..maxn] of pnode;
h:array[1..maxn] of hnode;
p,d:array[1..maxn] of longint;
inheap:array[1..maxn] of boolean;
n,m,size:longint;
procedure ins(e1,e2,e3:longint);
var tmp:pnode;
begin
new(tmp);
with tmp^ do begin
n:=e2;
w:=e3;
next:=g[e1];
end;
g[e1]:=tmp;
end;
procedure init;
var e1,e2,e3,i,j:longint;
begin
fillchar(d,sizeof(d),$3f);
fillchar(inheap,sizeof(inheap),true);
readln(n,m);
for i:=1 to m do begin
readln(e1,e2,e3);
ins(e1,e2,e3);
ins(e2,e1,e3);
end;
end;
procedure heap_init;
var i,j:longint;
k:hnode;
begin
size:=n;
for i:=1 to n do begin
with h[i] do begin
n:=i;
d:=longint($3f3f3f3f);
end;
p[i]:=i;
end;
h[1].d:=0;
end;
procedure siftup(i:longint);
var v:hnode;
dad:longint;
begin
v:=h[i]; dad:=i>>1;
while dad>0 do begin
if v.d<h[dad].d then begin
h[i]:=h[dad];
p[h[i].n]:=i;
i:=dad; dad:=i>>1;
end else break;
end;
h[i]:=v; p[h[i].n]:=i;
end;
procedure siftdown(i:longint);
var v:hnode;
kid:longint;
begin
v:=h[i]; kid:=i<<1;
while kid<=size do begin
if (kid<size)and(h[kid+1].d<h[kid].d) then inc(kid);
if h[kid].d<v.d then begin
h[i]:=h[kid];
p[h[i].n]:=i;
i:=kid; kid:=i<<1;
end else break;
end;
h[i]:=v; p[h[i].n]:=i;
end;
procedure deckey(i,j:longint);
begin
h[i].d:=j;
siftup(i);
end;
function extmin:hnode;
begin
extmin:=h[1];
inheap[h[1].n]:=false;
h[1]:=h[size];
dec(size);
p[h[1].n]:=1;
siftdown(1);
end;
procedure dijkstra;
var i:longint;
hmin:hnode;
tmp:pnode;
begin
for i:=1 to n do begin
hmin:=extmin;
if hmin.n=n then begin
writeln(hmin.d);
halt;
end;
//d[hmin.n]:=hmin.d;
tmp:=g[hmin.n];
while tmp<>nil do begin
if (tmp^.w+hmin.d<h[p[tmp^.n]].d)and(inheap[tmp^.n]) then
deckey(p[tmp^.n],tmp^.w+hmin.d);
tmp:=tmp^.next;
end;
end;
end;
begin
init;
heap_init;
dijkstra;
end.