10356  Rough Roads
Moderator: Board moderators
10356  Rough Roads
Hi!
Hmm.. This problem looked so simple ( Just to make Dijkstra on the graph with 2 times more edges and verticles...) but I can't get it Accepted...
Please help.. ( there is propably a stupid mistake
[pascal]
Sorry
[/pascal]
Hmm.. This problem looked so simple ( Just to make Dijkstra on the graph with 2 times more edges and verticles...) but I can't get it Accepted...
Please help.. ( there is propably a stupid mistake
[pascal]
Sorry
[/pascal]
Last edited by cyfra on Mon Sep 30, 2002 10:30 am, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
What do you mean with:
I didn't look at the code, I am no pascal programmer.
The problem is to find the shortest path consisting of an even number of edges, so you can't use the original edges, at least in my solution I couldn't.Just to make Dijkstra on the graph with 2 times more edges and verticles...
I didn't look at the code, I am no pascal programmer.
Yes I know....
This program is just the same as Dijkstra but each node we have to count twice  > when we came to it with odd or even number of moves...
and if in original graph nodes (u) and (v) were connected than in this graph there would be such connections:
u,1> v,2 v,2>u,1
u,2> v,1 v,1>u,2
And we have to find the shortest path from (0,1) to (n1,1)
I think I am right ... ( or maybe I'm not ?? )
This program is just the same as Dijkstra but each node we have to count twice  > when we came to it with odd or even number of moves...
and if in original graph nodes (u) and (v) were connected than in this graph there would be such connections:
u,1> v,2 v,2>u,1
u,2> v,1 v,1>u,2
And we have to find the shortest path from (0,1) to (n1,1)
I think I am right ... ( or maybe I'm not ?? )

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Sounds good, that algorithm should solve the problem. Perhaps try to initialize your array wart with 10001, because I think that there can be a case with exactly length 10000 as solution. Imagine a circle through 499 vertices and then the connection to n1. That are 500 connections with a length of at most 20, therefore a maximum of 10000 is possible.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I have the same trouble
My PASCAL code gets WA. I think it is only due FreePascal because my C++ code gets Accepted ! I've just wonder what can be wrong in code
(May be EOF works bad or something else?):
[pascal]Program p10356;
Const MaxN = 600;
Max = 1000000;
Var Inf : Array[1..2,0..MaxN]of Integer;
R : Array[0..MaxN,0..MaxN]of Integer;
C,N,M,j : Integer;
i,a,b,v : Integer;
begin
C:=0;
While Not Eof do begin
Readln(N,M);
for i:=1 to 2 do
for j:=0 to MaxN do Inf[i,j]:=Max;
for i:=0 to MaxN do
for j:=0 to MaxN do R[i,j]:=Max;
for i:=1 to M do begin
Readln(a,b,v);
R[a,b]:=v;
R[b,a]:=v;
end;
C:=C+1;
Writeln('Set #',C);
for i:=0 to N1 do Inf[1,i]:=R[0,i];
While True do begin
v:=0;
for i:=0 to N1 do
if Inf[1,i]<Max then
for j:=0 to N1 do
if Inf[1,i]+R[i,j]<Inf[2,j] then begin
v:=v+1;
Inf[2,j]:=Inf[1,i]+R[i,j];
end;
for i:=0 to N1 do
if Inf[2,i]<Max then
for j:=0 to N1 do
if Inf[2,i]+R[i,j]<Inf[1,j] then begin
v:=v+1;
Inf[1,j]:=Inf[2,i]+R[i,j];
end;
if v=0 then Break;
end;
v:=Inf[2,N1];
if v<Max then Writeln(v) else Writeln('?');
end;
end.[/pascal]
My PASCAL code gets WA. I think it is only due FreePascal because my C++ code gets Accepted ! I've just wonder what can be wrong in code
(May be EOF works bad or something else?):
[pascal]Program p10356;
Const MaxN = 600;
Max = 1000000;
Var Inf : Array[1..2,0..MaxN]of Integer;
R : Array[0..MaxN,0..MaxN]of Integer;
C,N,M,j : Integer;
i,a,b,v : Integer;
begin
C:=0;
While Not Eof do begin
Readln(N,M);
for i:=1 to 2 do
for j:=0 to MaxN do Inf[i,j]:=Max;
for i:=0 to MaxN do
for j:=0 to MaxN do R[i,j]:=Max;
for i:=1 to M do begin
Readln(a,b,v);
R[a,b]:=v;
R[b,a]:=v;
end;
C:=C+1;
Writeln('Set #',C);
for i:=0 to N1 do Inf[1,i]:=R[0,i];
While True do begin
v:=0;
for i:=0 to N1 do
if Inf[1,i]<Max then
for j:=0 to N1 do
if Inf[1,i]+R[i,j]<Inf[2,j] then begin
v:=v+1;
Inf[2,j]:=Inf[1,i]+R[i,j];
end;
for i:=0 to N1 do
if Inf[2,i]<Max then
for j:=0 to N1 do
if Inf[2,i]+R[i,j]<Inf[1,j] then begin
v:=v+1;
Inf[1,j]:=Inf[2,i]+R[i,j];
end;
if v=0 then Break;
end;
v:=Inf[2,N1];
if v<Max then Writeln(v) else Writeln('?');
end;
end.[/pascal]
I think that there is something worng with Judge System.
As I've written myself Judge System (not this ) I know that there is trouble with FPC and parameters. For example, if our solutions compile with no parameters it would all ok. (I'll try to compile mine code as "ppc386.exe prog.pas" and it work good, but if i compile it for Linux paltform it work very strange )
As I've written myself Judge System (not this ) I know that there is trouble with FPC and parameters. For example, if our solutions compile with no parameters it would all ok. (I'll try to compile mine code as "ppc386.exe prog.pas" and it work good, but if i compile it for Linux paltform it work very strange )
hi,
i think it's not the problem with FPC, it's just that the input data is badly formatted. Instead of readln, i use read, and i get AC using Pascal
so the input could be like this:
i think it's not the problem with FPC, it's just that the input data is badly formatted. Instead of readln, i use read, and i get AC using Pascal
so the input could be like this:
Code: Select all
3 3
0 1
10 0 2 10
1
2
10
10356Why WA???
I don't no why I always get WA?
My all test cases work well. I use dijkstra to solve this problem.
Is there are any tricky test case???
what does ur AC program give output for the following testcase:
4 4
0 3 1
0 1 1
1 2 1
2 0 1
I need ur help.
My all test cases work well. I use dijkstra to solve this problem.
Is there are any tricky test case???
what does ur AC program give output for the following testcase:
4 4
0 3 1
0 1 1
1 2 1
2 0 1
I need ur help.
hi sojib,
your sample input is:
one way is straight gate to grand father's home, so it is not acceptable as he reaches his grand father's home carrying the cycle on his back.
and the another answer is 4 ( after traversing 3 junction and his grand father's home at 4th junction);
so the answer for your input is > 4
I also solved this problem using only Disktra's algorithm. but what i have heard, there is other simple way to solve this problem, if we proceed simple calculation with the adjency matrix.
your sample input is:
There is two way to reach grand father's home from gate .4 4
0 3 1
0 1 1
1 2 1
2 0 1
one way is straight gate to grand father's home, so it is not acceptable as he reaches his grand father's home carrying the cycle on his back.
He also decided to start his journey by carrying the cycle on his back, not by riding it.
and the another answer is 4 ( after traversing 3 junction and his grand father's home at 4th junction);
so the answer for your input is > 4
I also solved this problem using only Disktra's algorithm. but what i have heard, there is other simple way to solve this problem, if we proceed simple calculation with the adjency matrix.
__nOi.m....