11015 - 05-2 Rendezvous

[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

[sclo]

I think that's clear from the question, we consider also indirect paths.

[Niaz]

Though I feel this one an easy problem, but getting WA
Here is my code... anyone can find my bug ? Thanx in advance.

Code: Select all

Accepted :)


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

[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

[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

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

[neno_uci]

(1^2 - 1) / 2 == 0

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

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

[sohel]

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

[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



[ayon]

the line
memset(mat[i],INF,MAX+1);
wont fill all elements of mat[i] with 999999, it will fill a garbage value.
and better if you dont post your full ID with suffix

[shihabrc]

Thanx 4 ur hlp. Got AC now.

I really forgot 2 remove my ID frm the code.

[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

[Martin Macko]

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:

for(i=1;i<=b;i++){scanf("%ld%ld%ld",&c,&d,&p);
........adj[c][d]=p;
........adj[d][c]=p;
}