10356 - Rough Roads

[cyfra]

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]

[Adrian Kuegel]

What do you mean with:

Just to make Dijkstra on the graph with 2 times more edges and verticles...

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.
I didn't look at the code, I am no pascal programmer.

[cyfra]

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 (n-1,1)

I think I am right ... ( or maybe I'm not ?? )

[Adrian Kuegel]

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 n-1. That are 500 connections with a length of at most 20, therefore a maximum of 10000 is possible.

[cyfra]

Hmm....

But this array already is initialized with 10000 ...

I don't think that there can be a bigger solution ....

So why it doesn't work ??

[Adrian Kuegel]

Sorry, I didn't look careful at it, I thought it was 10000. Don't know there a mistake can be, pascal looks so strange to me.

[cyfra]

Don't worry


But do you know if there are any trick cases in this program ???

Because for all my tests this program gave correct answers..

[Revenger]

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 N-1 do Inf[1,i]:=R[0,i];
While True do begin
v:=0;
for i:=0 to N-1 do
if Inf[1,i]<Max then
for j:=0 to N-1 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 N-1 do
if Inf[2,i]<Max then
for j:=0 to N-1 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,N-1];
if v<Max then Writeln(v) else Writeln('?');
end;
end.[/pascal]

[cyfra]

The MUST be something wrong in this task with Pascal..

(note that there is no Pascal program Accepted ... )

Maybe Judge can check it, whether it is FP compiler error ??

[Revenger]

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 )

[arc16]

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:

Code: Select all

       3             3
0          1 
10  0       2     10
     1 
2 
10

[cyfra]

Judges have changed something and checked all programs again...

I have Accepted at last...


Thanks to all for help

[shojib]

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.

[Noim]

hi sojib,

your sample input is:

4 4
0 3 1
0 1 1
1 2 1
2 0 1

There is two way to reach grand father's home from gate .
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.

[shojib]

4 4
0 3 1
0 1 1
1 2 1
2 0 1
But here he has to visit the starting vertex twice, as he has to travel
with even number of edges. But as far as I know in dijkstra's algorithm
a vertex is explored only once. So, it is becoming tough for me to handle
this situation with this algorithm.