ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1205. By the Underground or by Foot?

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.