I'v got WA1 ! Why ?
This problem have Checker ? My answer is
2.6346295
4 2 1 3 5.
I check my answer , it is optimal! I don't understand it!
My code :
var
a:array[0..300,0..300]of extended;
q,w,i,j,num,n,k,aa,bb:longint;
u:array[0..300]of boolean;
s:array[0..300]of longint;
pr:array[0..300,0..300]of longint;
x,y:array[0..300]of extended;
min,x1,y1,x2,sum,y2,s1,s2:extended;
function dist(x1,y1,x2,y2:extended):extended;
begin
dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
begin
// assign(input,'input.txt');reset(input);
// assign(output,'output.txt');rewrite(output);
read(s1,s2);
read(n);
for i:=1 to n do read(x[i],y[i]);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=dist(x[i],y[i],x[j],y[j])/s1;
read(q,w);
while (q+w>0)do
begin
a[q,w]:=dist(x[q],y[q],x[w],y[w])/s2;
a[w,q]:=dist(x[w],y[w],x[q],y[q])/s2;
read(q,w);
end;
read(x1,y1,x2,y2);
a[0,n+1]:=dist(x1,y1,x2,y2)/s1;
for i:=1 to n do
begin
a[0,i]:=dist(x1,y1,x[i],y[i])/s1;
a[i,n+1]:=dist(x2,y2,x[i],y[i])/s1;
end;
for i:=1 to n+1 do
begin
pr[i,0]:=1;
pr[i,1]:=i;
end;
fillchar(pr,sizeof(pr),0);
fillchar(u,sizeof(u),true);
for i:=0 to n+1 do
begin
num:=1;
min:=10000;
for j:=n+1 downto 0 do
if u[j] and (a[0,j]<min)then
begin
min:=a[0,j];
num:=j;
end;
u[num]:=false;
for j:=1 to n+1 do
if (a[0,num]+a[num,j]<a[0,j])then
begin
a[0,j]:=a[0,num]+a[num,j];
pr[j]:=pr[num];
inc(pr[j,0]);
pr[j,pr[j,0]]:=j;
end;
end;
writeln(a[0,n+1]:0:7);
write(pr[n+1,0]);
for i:=1 to pr[n+1,0]do
write(' ',pr[n+1,i]);
writeln;
end.
