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

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

I've Used Dijkstra But WA
Послано SoSimple 13 ноя 2007 18:37
I've Used Dijkstra But I'm Getting WA On Test1 And I Know That The Test1 Is The Sample Test And My Program Gives The Right Answer

This Is My Code

Program Underground;
{$APPTYPE CONSOLE}
Uses
  SysUtils;
Var
  d:array[0..201,0..201] of double;
  dd:array[0..201] of double;
  p:array[0..201] of integer;
  n:integer;
Procedure InputData;
Var
  i,j,t1,t2:integer;
  feet,under:double;
  x,y:array[0..201] of double;
begin
  assign(input,'');
  reset(input);
  readln(feet,under);
  readln(n);
  for i:=1 to n do
  begin
    readln(x[i],y[i]);
  end;
  for i:=1 to n-1 do
    for j:=i+1 to n do
    begin
      d[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))/feet;
      d[j,i]:=d[i,j];
    end;
  while (true) do
  begin
    readln(t1,t2);
    if (t1=t2) and (t1=0) then break;
    d[t1,t2]:=sqrt(sqr(x[t1]-x[t2])+sqr(y[t1]-y[t2]))/under;
    d[t2,t1]:=d[t1,t2];
  end;
  readln(x[0],y[0]);
  readln(x[n+1],y[n+1]);
  for i:=0 to N+1 do
  begin
    d[0,i]:=sqrt(sqr(x[0]-x[i])+sqr(y[0]-y[i]))/feet;
    d[i,0]:=d[0,i];
    d[n+1,i]:=sqrt(sqr(x[n+1]-x[i])+sqr(y[n+1]-y[i]))/feet;
    d[i,n+1]:=d[n+1,i];
  end;
   close(input);
end;
Procedure Dijkstra;
Var
  i,u:Integer;
  min:double;
  T:Set Of 0..201;
Begin
  For i:=0 To N+1 Do
  begin
    dd[i]:=d[0,i ] ;
    p[i]:=0;
  end;
  T:=[0..N+1]-[0];
  u:=n+1;
  While T<>[] Do Begin
    min:=1.7e+308;
    for i:=0 to N+1 do
      if (i In T) and (dd[i]<min) then
      begin
        u:=i;
        min:=dd[i];
      end;
    T:=T-[u];
    For i:=0 To N+1 Do
    If (i In T)and((dd[u]+d[u,i])<dd[i]) Then
    begin
      dd[i]:=dd[u]+d[u,i];
      p[i]:=u;
    end;
  End;
End;
Procedure OutputData;
Var nn:integer;
  Procedure outputForN(i:integer);
  begin
    if i<>0 then outputForn(p[i]);
    inc(nn);
  end;
  Procedure outputforP(i:integer);
  begin
    if p[i]<>0 then outputforP(p[i]);
    if i<>N+1 then  write(' ',i);
  end;
begin
  assign(output,'');
  rewrite(output);
  Writeln(dd[n+1]:0:7);
  Outputforn(n+1);
  write(nn-2);
  OutputforP(n+1);
  close(output);
end;
Begin
  InputData;
  Dijkstra;
  OutputData;
End.
Re: I've Used Dijkstra But WA
Послано SoSimple 15 ноя 2007 18:16
Please Help Nobody Wants To Help Me
Re: I've Used Dijkstra But WA
Послано 6yxa/\bl 17 ноя 2007 13:18
But in another problem i have used 4 Dijkstra's and got AC :)
Re: I've Used Dijkstra But WA
Послано whywaidontknow 18 ноя 2007 12:25
you need to initialize nn; nn is local variable
and it's value is "random" before you initialize it.
add line nn := 0; before Outputforn(n+1); an you got AC
Re: I've Used Dijkstra But WA
Послано Alias (Alexander Prudaev) 18 ноя 2007 12:29
whywaidontknow is my dirty account
Re: I've Used Dijkstra But WA
Послано whywaidontknow 18 ноя 2007 12:30
yes i am dirty account of Alias
Re: I've Used Dijkstra But WA
Послано SoSimple 25 ноя 2007 16:25
Thanx I've Got Accepted