讨论 / 谁来帮帮忙dijkstra+heap
zhhyoi 2010-06-08 00:56:00
点我顶贴 收藏 删除
我这个怎么改能过

program Project1;

type heap=record

id:integer;

nm:longint;

end;

var inheap:array[0..30000]of boolean;

heappos:array[0..30000]of integer;

h:array[0..30000]of heap;

map,mindis:array[0..30000,0..30000]of integer;

g:array[0..30000,0..8000]of integer;

x,y,z,min,i,j,k,size,n,m,q:longint;

procedure swap(var i,j:heap);

var t:heap;

begin

t:=i;

i:=j;

j:=t;

end;

//----------------------------------------------

procedure down(x:longint);

var y:longint;

begin

if (x*2<=size)and(h[x*2].nm<h[x].nm) then y:=x*2 else y:=x;

if (x*2+1<=size)and(h[x*2+1].nm<h[y].nm) then y:=x*2+1;

if y<>x then

begin

heappos[h[x].id]:=y;

heappos[h[y].id]:=x;

swap(h[y],h[x]);

down(y);

end;

end;

//----------------------------------------------

procedure up(x:longint);

begin

while (x>1)and(h[x].nm<h[x shr 1].nm) do

begin

heappos[h[x].id]:=x shr 1;

heappos[h[x shr 1].id]:=x;

swap(h[x],h[x shr 1]);

x:=x shr 1;

end;

end;

//----------------------------------------------

procedure getmin(var min,id:longint);

begin

min:=h[1].nm; id:=h[1].id;

heappos[h[1].id]:=size;

heappos[h[size].id]:=1;

swap(h[1],h[size]);

dec(size);

end;

//---------------------------------------------

procedure dijkstra(f:longint);

begin

size:=n;

for i:=1 to n do

begin

h[i].nm:=maxlongint shr 2;

heappos[i]:=i;

h[i].id:=i;

end;

fillchar(inheap,sizeof(inheap),0);

h[f].nm:=0;

up(f);

for i:=1 to n do

begin

getmin(min,k);

inheap[k]:=true;

mindis[f,k]:=min; mindis[k,f]:=min;

down(1);

for j:=1 to g[k,0] do

begin

q:=g[k,j];

if not inheap[q] and(h[heappos[q]].nm>min+map[k,q])

then begin

h[heappos[q]].nm:=min+map[k,q];

up(heappos[q]);

end;

end;

end;

end;

//--------------------------------------------------

begin

assign(input,'dijkstra.in');

assign(output,'dijkstra.out');

reset(input);

rewrite(output);

readln(n,m);

for i:=1 to m do

begin

readln(x,y,z);

inc(g[x,0]); g[x,g[x,0]]:=y;

inc(g[y,0]); g[y,g[y,0]]:=x;

map[x,y]:=z; map[y,x]:=z;

end;

dijkstra(1);

writeln(mindis[1,n]);

close(input);

close(output);

end.

#1 hantx@2017-10-07 00:19:32
回复 删除
三万的平方,九亿,Dijkstra数据用邻接矩阵存,你连数据都存不下,稀疏图一个啊
查看更多回复
提交回复