问题在于,为什么我第八个点和第九个点是输出长度超出标准,标准输出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.