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

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

1205
Послано Zhang Ruiwen 9 апр 2002 15:59
why I get WA?
who can help me?

---------------------------------------------

type rr=array[0..201] of real;
var n:integer;
    a:array[0..201] of ^rr;
    sr,st,xa,ya,xb,yb:real;

procedure init;
var i,j,s,e:integer;
    poi:array[1..200,1..2] of real;
begin
 readln(sr,st);
 readln(n);
 for i:=1 to n do
 begin
  readln(poi[i,1],poi[i,2]);
  new(a[i]);
  for j:=1 to i-1 do
  begin
   a[i]^[j]:=sqrt(abs(sqr(poi[i,1]-poi[j,1])+sqr(poi[i,2]-poi
[j,2])))/sr;
   a[j]^[i]:=a[i]^[j];
  end;
 end;
 readln(s,e);
 while s<>0 do
 begin
  a[s]^[e]:=sqrt(abs(sqr(poi[s,1]-poi[e,1])+sqr(poi[s,2]-poi
[e,2])))/st;
  a[e]^[s]:=a[s]^[e];
  readln(s,e);
 end;
 readln(xa,ya);
 readln(xb,yb);
 new(a[0]);
 new(a[n+1]);
 for i:=1 to n do
 begin
  a[0]^[i]:=sqrt(abs(sqr(xa-poi[i,1])+sqr(ya-poi[i,2])))/sr;
  a[n+1]^[i]:=sqrt(abs(sqr(xb-poi[i,1])+sqr(yb-poi[i,2])))/sr;
  a[i]^[0]:=a[0]^[i];
  a[i]^[n+1]:=a[n+1]^[i];
 end;
 a[0]^[n+1]:=sqrt(abs(sqr(xa-xb)+sqr(ya-yb)))/sr;
 a[n+1]^[0]:=a[0]^[n+1];
end;

procedure main;
var i,j,bi:integer;
    s:set of byte;
    now:array[0..201] of real;
    last,ans:array[0..201] of integer;
    min:real;
begin
 for i:=1 to n+1 do
 begin
  now[i]:=a[0]^[i];
  last[i]:=0;
 end;
 s:=[];
 for i:=1 to n+1 do
 begin
  min:=100000;
  for j:=1 to n+1 do
  if (not (j in s))and(now[j]<min) then
  begin
   min:=now[j];
   bi:=j;
  end;
  s:=s+[bi];
  for j:=1 to n+1 do
  if (not (j in s))and(now[bi]+a[bi]^[j]<now[j]) then
  begin
   now[j]:=now[bi]+a[bi]^[j];
   last[j]:=bi;
  end;
 end;
 writeln(now[n+1]:0:7);
 i:=n+1;
 j:=0;
 while i<>0 do
 begin
  j:=j+1;
  ans[j]:=i;
  i:=last[i];
 end;
 write(j-1,' ');
 for i:=j downto 2 do write(ans[i],' ');
 writeln;
end;

begin
 init;
 main;
end.