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

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

Help me!!!!!!!!!!
Послано SNU 16 апр 2009 00:27
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.
Re: Help me!!!!!!!!!!
Послано Partisan 15 июн 2009 15:45
2.6346295
4 2 1 3 >>5<<
There are only 4 stations in underground.