10356 - Rough Roads

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

10356 - Rough Roads

Post by cyfra » Wed Sep 18, 2002 1:09 pm

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 :wink:
[/pascal]
Last edited by cyfra on Mon Sep 30, 2002 10:30 am, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 18, 2002 4:47 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Sep 19, 2002 7:42 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Sep 19, 2002 2:56 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Sep 19, 2002 3:01 pm

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 ?? :cry:

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Sep 19, 2002 3:07 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Sep 19, 2002 3:09 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Fri Sep 20, 2002 7:25 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Fri Sep 27, 2002 11:37 am

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Sat Sep 28, 2002 1:02 pm

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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sat Sep 28, 2002 1:58 pm

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 :wink:

so the input could be like this:

Code: Select all

       3             3
0          1 
10  0       2     10
     1 
2 
10

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Mon Sep 30, 2002 10:30 am

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

I have Accepted at last...


Thanks to all for help 8)

shojib
New poster
Posts: 2
Joined: Mon Jun 24, 2002 11:34 pm
Location: Bangladesh
Contact:

10356-Why WA???

Post by shojib » Wed Jun 11, 2003 4:59 am

I don't no why I always get WA? :x
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
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Wed Jun 11, 2003 6:57 pm

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.
__nOi.m....

shojib
New poster
Posts: 2
Joined: Mon Jun 24, 2002 11:34 pm
Location: Bangladesh
Contact:

Post by shojib » Wed Jun 11, 2003 9:42 pm

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. :cry:

Post Reply

Return to “Volume 103 (10300-10399)”