讨论 / PID676 求助!
初学者123 2013-05-14 08:37:00
点我顶贴 收藏 删除
求第k+1短路径,思路大概就是从第一个节点开始搜,用堆来维护当期各节点与1的距离,第n个节点第k+1次出堆时即为最短路径。

问题在于,为什么我第八个点和第九个点是输出长度超出标准,标准输出4位我输出了97位。。。我的程序里只有一句writeln(dis);之后马上halt掉,为什么会有这种输出?

附程序:(sift,insert,delete为维护堆的各个操作,swap交换两个堆节点,expand从当前堆的第一个节点进行扩展)

program rqn676;

uses

math;

type

heapnode=record

node:longint;

dis:int64;

end;

link=^linknode;

linknode=record

node:longint;

dis:int64;

next:link;

end;

var

heap:array[0..50000]of heapnode;

edge:array[0..6000]of link;

templength,longest,outtime:array[0..6000]of int64;

n,k,heapsize:longint;

procedure init;

var

i,r,u,v,d:longint;

p:link;

begin

readln(n,r,k);

for i:=1 to n do

edge[i]:=nil;

for i:=1 to r do

begin

readln(u,v,d);

new(p);

p^.node:=v;

p^.dis:=d;

p^.next:=edge[u];

edge[u]:=p;

new(p);

p^.node:=u;

p^.dis:=d;

p^.next:=edge[v];

edge[v]:=p;

end;

heapsize:=1;

fillchar(outtime,sizeof(outtime),0);

fillchar(longest,sizeof(longest),0);

fillqword(templength,sizeof(templength)div 8,-1);

heap[1].node:=1;

heap[1].dis:=0;

end;

procedure swap(var a,b:heapnode);

var

t:heapnode;

begin

t:=a;

a:=b;

b:=t;

end;

procedure sift(t:longint);

begin

if t>heapsize>>1 then

exit;

if (t=heapsize>>1)and(heapsize and 1=1) then

if heap[t].dis>heap[heapsize].dis then

begin

swap(heap[t],heap[heapsize]);

exit;

end;

if (heap[t].dis<heap[t<<1].dis)and(heap[t].dis<heap[t<<1+1].dis) then

exit;

if heap[t<<1].dis<heap[t<<1+1].dis then

begin

swap(heap[t],heap[t<<1]);

sift(t<<1);

end

else

begin

swap(heap[t],heap[t<<1+1]);

sift(t<<1+1);

end;

end;

procedure insert(i,distan:longint);

var

t:longint;

begin

inc(heapsize);

heap[heapsize].node:=i;

heap[heapsize].dis:=distan;

t:=heapsize;

while t>1 do

if heap[t].dis<heap[t>>1].dis then

begin

swap(heap[t],heap[t>>1]);

t:=t>>1;

end

else

break;

end;

procedure delete(i:longint);

begin

swap(heap[i],heap[heapsize]);

dec(heapsize);

sift(1);

end;

procedure expand(t:longint);

var

p:link;

begin

with heap[t] do

begin

new(p);

p:=edge[node];

while p<>nil do

begin

if not((outtime[p^.node]>k)and(dis+p^.dis>longest[p^.node]))

and (templength[p^.node]<>dis+p^.dis) then

begin

insert(p^.node,p^.dis+dis);

longest[p^.node]:=max(longest[p^.node],dis+p^.dis);

end;

p:=p^.next;

end;

end;

end;

procedure main;

begin

while true do

with heap[1] do

begin

if dis=templength[node] then

begin

delete(1);

continue;

end;

if (node=n)and(outtime[n]=k) then

begin

writeln(dis);

halt;

end;

expand(1);

inc(outtime[node]);

templength[node]:=dis;

delete(1);

end;

end;

begin

init;

main;

end.

查看更多回复
提交回复