10449  Traffic
Moderator: Board moderators

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Dominik, I think we share the same confusion here ...
I also added the check to return '?' if the junction number is out of range. Still doesn't help ... any other ideas ???
I also use BellmanFord algorithm for this. Unreachable junction will return '?'.
Thanks for any comment ...
turuthok
I also added the check to return '?' if the junction number is out of range. Still doesn't help ... any other ideas ???
I also use BellmanFord algorithm for this. Unreachable junction will return '?'.
Thanks for any comment ...
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Larry, I'm pretty sure I checked negative cycles as well. Correct me if I'm wrong but after I ran BellmanFord for ncycles ... I would have a list of distances from junction 1 ... Whenever I see an element with < 3 ... I'll print '?'. Same output for unreachable junctions ...
Thanks for your comment,
turuthok
Thanks for your comment,
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
turuthok  perhaps you have an error similar to the one i had. i used code like:
path=infinity....... or (1<<30)
then
improve all paths
then.....
if(path<infinity)....
however this didnt work because i had been improving paths, and adding negatives to the infinity value i used, in the end i sorted it with
if(path<lower_inf)..... or (1<<29)....
(it only got added to the 'inf' value because there was a path from i to j which was negative weight and so this was an 'improvement'......
path=infinity....... or (1<<30)
then
improve all paths
then.....
if(path<infinity)....
however this didnt work because i had been improving paths, and adding negatives to the infinity value i used, in the end i sorted it with
if(path<lower_inf)..... or (1<<29)....
(it only got added to the 'inf' value because there was a path from i to j which was negative weight and so this was an 'improvement'......

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
I think that d can still be positive after the ncycle BellmannFord.
So I found all vertices which were in the condition
for all edges (u, v)
d[v] > d+w(u, v)
and marked all vertices which were reachable from v, with INFINITE.
And Caesum's comments were essential. Thank you, Caesum! =)
(Actually wrote this reply to thank him
So I found all vertices which were in the condition
for all edges (u, v)
d[v] > d+w(u, v)
and marked all vertices which were reachable from v, with INFINITE.
And Caesum's comments were essential. Thank you, Caesum! =)
(Actually wrote this reply to thank him

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
modified BellmanFord
There's a nice simple modification to BellmanFord which will give perfect results in the presence of negative cycles without needing any postprocessing.
Simply run BellmanFord for 2n cycles (instead of n), but after the first n iterations start relaxing everything to infinity (since anything which hasn't stabilized must be on a negative cycle). Within 2n cycles everything will have converged.
As usual, you can shortcut the process as soon as everything has stabilized.
Simply run BellmanFord for 2n cycles (instead of n), but after the first n iterations start relaxing everything to infinity (since anything which hasn't stabilized must be on a negative cycle). Within 2n cycles everything will have converged.
As usual, you can shortcut the process as soon as everything has stabilized.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Thanks for nice hint
BTW. It's neccessary to run to 2*N BellmanFord algorithm ? Maybe is enough to run this algorithm only N+1 times, and in N+1 run change states of every lengths, which vary to infinity ?
Could anyone tell me: I'm right or I'm wrong?
Regards
Dominik
BTW. It's neccessary to run to 2*N BellmanFord algorithm ? Maybe is enough to run this algorithm only N+1 times, and in N+1 run change states of every lengths, which vary to infinity ?
Could anyone tell me: I'm right or I'm wrong?
Regards
Dominik
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
10449
thanx to both DM and Chung, I have found the bug in my pro , making sure the value of Len must not transcend the Limit.
But I wonder whether there are some improvement to accelerate
the running speed?
But I wonder whether there are some improvement to accelerate
the running speed?
Last edited by WanBa on Thu Jun 19, 2003 5:25 pm, edited 1 time in total.
destiny conditioned by past

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
I also use bellmanford to do this problem, but i got many WAs.....
I had try many test cases, such as negative cycle, disconnect path.... But i still don't know what is my mistake, can anyone post some test data here??( which may helpful for me to find my mistake and got AC!!)
thank you very much
I had try many test cases, such as negative cycle, disconnect path.... But i still don't know what is my mistake, can anyone post some test data here??( which may helpful for me to find my mistake and got AC!!)
thank you very much
Last edited by Chow Wai Chung on Thu Jun 19, 2003 4:32 am, edited 3 times in total.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
to both of us:
search board FIRST, and after that post our threads... answer for our questions are included in other threads
Best regards
DM
search board FIRST, and after that post our threads... answer for our questions are included in other threads
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
Dominik, thank you for your remind.
But i had search for this problem on this board and consider those mistake may exist on my program before, but i still don't know where is my mistakes, and i found someone ask a new question on this problem, so i add my problem to this thread.
If anyone don't mind, please send me your test data.
Thank you
But i had search for this problem on this board and consider those mistake may exist on my program before, but i still don't know where is my mistakes, and i found someone ask a new question on this problem, so i add my problem to this thread.
If anyone don't mind, please send me your test data.
Thank you

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong