ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1205. На метро или пешком?

Why wrong answer? Give me some test data please.
Послано aaa 23 мар 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.