Page 1 of 4

11015 - 05-2 Rendezvous

Posted: Sun Apr 09, 2006 9:05 pm
by Peter3109
For the test data there is only one house that is directly connected to the rest (house 1). Does this mean that house 1 is the only possible meeting place or can people travel to other houses indirectly by using a series of connected houses?

Thanks!

Peter

Posted: Tue Apr 11, 2006 12:40 am
by sclo
I think that's clear from the question, we consider also indirect paths.

Posted: Mon Apr 17, 2006 4:46 pm
by Niaz
Though I feel this one an easy problem, but getting WA :cry:
Here is my code... anyone can find my bug ? Thanx in advance.

Code: Select all

Accepted :) 

Posted: Mon Apr 17, 2006 4:59 pm
by mf
Your implementation of Floyd-Warshall algorithm is incorrect.
And you also don't handle multiple edges between same pair of vertices correctly (but I don't know if judge's input has such test cases, so it may not be a problem)

Posted: Mon Apr 17, 2006 10:44 pm
by arsalan_mousavian
your fluid algorithm is incorrect , the correct order of your loop is k , i , j where k is outer loop and j is inner loop

Posted: Thu Apr 20, 2006 11:28 am
by Niaz
Thanks to mf and arsalan_mousavian.

I am such a duffer! I used so many times FW but never did this mistake and how come I did it here ? Interestingly it gave the correct output for the sample inputs and that made me more crazy. I checked lot many things in my code (even thought about multiple paths also) but didn

11015 - 05-2 Rendezvous

Posted: Thu May 04, 2006 11:02 am
by forgotten
when my program used

while (scanf("%d%d", &n, &m) == 2 && n && m) {...}

to read the data, i got WA

but when i use

while (scanf("%d%d", &n, &m), n) {...}

or

while (scanf("%d%d", &n, &m) == 2 && n) {...}

i've got AC !!

could M equal ZERO ??

notice 1 ? M ? (N^2-N)/2 !!

could anyone give me an explanation to this strange problem ?

Posted: Sat May 06, 2006 3:57 am
by neno_uci
(1^2 - 1) / 2 == 0 :D

Maybe that could happen, btw i used while n > 0 :wink:

Posted: Sun Jun 18, 2006 9:14 am
by Kallol
I used Dijkstra to solve this problem ..
The answers of the test cases were right but I got WA when I submitted.

Is Dijkstra not the proper algorithm here ??

Posted: Sun Jun 18, 2006 9:42 am
by sohel
kallol wrote: Is Dijkstra not the proper algorithm here ??
How are you using Dijkstra here? :-?

Which node are you considering as the source??
If you are running N different dijkstras, considering every node as a src, then it should work..
.. but then again, why aren't you uisng Floyd-Warshall here.

FW is the most obvious one here........ at least, that's how I did it !!

11015 - 05-2 Rendezvous

Posted: Wed Jul 19, 2006 8:57 pm
by shihabrc
Though its a straigh forward Floyd Warshall problem, I'm getting WA with it. I've run FW and then searched the house from where maximum houses are reacheable and then chosen the ont with the minimal distance. But getting WA. Can some1 hlp plz.I'm giving the code.

Code: Select all


removed after AC


Posted: Thu Jul 20, 2006 7:27 am
by ayon
the line
memset(mat,INF,MAX+1);
wont fill all elements of mat with 999999, it will fill a garbage value.
and better if you dont post your full ID with suffix

Posted: Thu Jul 20, 2006 8:14 pm
by shihabrc
Thanx 4 ur hlp. Got AC now.

I really forgot 2 remove my ID frm the code. :oops:

help me

Posted: Sat Jul 22, 2006 9:50 pm
by tuman
hi , i cant do anything more with 11015. No input output available in board. So i m bound to show my code. Plz help me out. I m getting wrong answer....plz help

plz send some critical i\o


Code: Select all


code removed after A.C   
thanx in advance

Re: help me

Posted: Sun Jul 23, 2006 6:42 pm
by Martin Macko
tuman wrote:hi , i cant do anything more with 11015. No input output available in board. So i m bound to show my code. Plz help me out. I m getting wrong answer....plz help
There may be multiple edges between two vertices. At least, the problem statement does not say there are no such multiple esges. Maybe this is the reason of getting WA.

Try to change tho following code to remember the shortest edge between two edges:
your code wrote:for(i=1;i<=b;i++){scanf("%ld%ld%ld",&c,&d,&p);
........adj[c][d]=p;
........adj[d][c]=p;
}