Why wrong answer? Give me some test data please.
Posted by
aaa 23 Mar 2002 05:48
{$n+}
const nnn=200;
zero=1e-20;
v=10000;
var n,nn,a,d,f,i:integer; v1,v2:double;
b:array[1..nnn+2,1..2] of double;
c:array[1..nnn+2,1..nnn+2] of double;
e:array[1..nnn+2] of double;
g:array[1..nnn+2] of boolean;
h,j:array[1..nnn+2] of shortint;
procedure z;
var a1,b1:double; c1:integer;
begin
read(a1,b1);
for c1:=1 to n do
if (b[c1,1]=a1)and(b[c1,2]=b1) then break;
if (b[c1,1]=a1)and(b[c1,2]=b1) then d:=c1
else begin
inc(n); b[n,1]:=a1; b[n,2]:=b1;
for c1:=1 to n-1 do begin
c[c1,n]:=sqrt(sqr(b[c1,1]-a1)+sqr(b[c1,2]-b1))/v1;
c[n,c1]:=c[c1,n];
end;
c[n,n]:=0;
d:=n;
end;
end;
begin
assign(input,''); reset(input);
assign(output,''); rewrite(output);
read(v1,v2); v1:=v1/v; v2:=v2/v;
read(n); nn:=n;
for a:=1 to n do read(b[a,1],b[a,2]);
for a:=1 to n-1 do begin
c[a,a]:=0;
for d:=a+1 to n do begin
c[a,d]:=sqrt(sqr(b[a,1]-b[d,1])+sqr(b[a,2]-b[d,2]))/v1;
c[d,a]:=c[a,d];
end;
end;
read(a,d);
while (a<>0)and(d<>0) do begin
c[a,d]:=c[a,d]*v1/v2; c[d,a]:=c[a,d];
read(a,d);
end;
z; a:=d; z;
for f:=1 to n do begin
e[f]:=c[a,f]; h[f]:=a;
end;
h[a]:=0;
fillchar(g,sizeof(g),true);
while g[d] do begin
i:=0;
for f:=1 to n do
if g[f] and((i=0)or(e[f]<e[i]+zero)) then i:=f;
g[i]:=false;
for f:=1 to n do
if g[f] and(e[i]+c[i,f]<e[f]+zero) then begin
e[f]:=e[i]+c[i,f]; h[f]:=i;
end;
end;
writeln(e[d]/v:0:7);
f:=0;
repeat
if d<=nn then begin
inc(f); j[f]:=d;
end;
d:=h[d];
until d=0;
write(f);
for a:=f downto 1 do write(' ',j[a]);
writeln;
close(input); close(output);
end.