ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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);
for i:=1 to n do
begin
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
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;
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
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