ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1205. By the Underground or by Foot?

I've Used Dijkstra But WA
Posted by SoSimple 13 Nov 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
Posted by SoSimple 15 Nov 2007 18:16
Please Help Nobody Wants To Help Me
Re: I've Used Dijkstra But WA
Posted by 6yxa/\bl 17 Nov 2007 13:18
But in another problem i have used 4 Dijkstra's and got AC :)
Re: I've Used Dijkstra But WA
Posted by whywaidontknow 18 Nov 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
Posted by Alias (Alexander Prudaev) 18 Nov 2007 12:29
whywaidontknow is my dirty account
Re: I've Used Dijkstra But WA
Posted by whywaidontknow 18 Nov 2007 12:30
yes i am dirty account of Alias
Re: I've Used Dijkstra But WA
Posted by SoSimple 25 Nov 2007 16:25
Thanx I've Got Accepted