讨论 / 邻接表+Heap Dijkstra 过
Hoblovski 2013-11-06 23:50:29
点我顶贴 收藏 删除
这算基本算法了吧 应该不需要讲解了

注意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.

查看更多回复
提交回复