## 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

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

[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:
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
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 ?? )

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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
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
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
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
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
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
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Judges have changed something and checked all programs again...

I have Accepted at last...

Thanks to all for help

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

### 10356-Why 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.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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