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

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

Why wa #4?
Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 25 сен 2004 15:20
program ural1205;
const
  maxn=200;
var
  x,y:array[1..maxn]of real;
  dist,path:array[1..maxn,1..maxn]of real;
  pre:array[1..maxn,1..maxn]of byte;
  route:array[1..maxn]of byte;
  vfoot,vtrain,xa,ya,xb,yb,min,t:real;
  n,i,j,k,l:byte;
begin
  read(vfoot,vtrain,n);
  for i:=1 to n do
    read(x[i],y[i]);
  for i:=1 to n do
    for j:=1 to n do begin
      dist[i,j]:=1e38;
      path[i,j]:=1e38;
      pre[i,j]:=i;
    end;
  repeat
    read(i,j);
    if i=0 then break;
    dist[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));dist[j,i]:=dist[i,j];
    path[i,j]:=dist[i,j];path[j,i]:=dist[j,i];
  until false;
  read(xa,ya,xb,yb);

  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if path[i,k]+path[k,j]<path[i,j] then begin
          path[i,j]:=path[i,k]+path[k,j];
          pre[i,j]:=pre[k,j];
        end;

  min:=sqrt(sqr(xa-xb)+sqr(ya-yb))/vfoot;
  for i:=1 to n do
    for j:=1 to n do begin
      t:=(sqrt(sqr(xa-x[i])+sqr(ya-y[i]))+
          sqrt(sqr(xb-x[j])+sqr(yb-y[j])))/vfoot+
         path[i,j]/vtrain;
      if t<min then begin
        min:=t;k:=i;l:=j;
      end;
    end;
  writeln(min:0:7);
  if l=0 then
    writeln(0)
  else if k=l then
    writeln(1,' ',k)
  else begin
    i:=1;route[1]:=l;
    repeat
      inc(i);
      l:=pre[k,l];
      route[i]:=l;
    until l=k;
    write(i);
    for j:=i downto 1 do
      write(' ',route[j]);
    writeln;
  end;
end.
Re: Why wa #4?
Послано George_Aloyan[PTS Obninsk] 14 янв 2012 16:57
If you have WA 4 just think, that not all stations must be reached from each other, so you can go from station to station on foot
Re: Why wa #4?
Послано IgorKoval(from Pskov) 15 фев 2012 22:33
George_Aloyan[PTS Obninsk] писал(a) 14 января 2012 16:57
If you have WA 4 just think, that not all stations must be reached from each other, so you can go from station to station on foot

Perfect idea! Thank you.