11015 - 05-2 Rendezvous

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

Moderator: Board moderators

Peter3109
New poster
Posts: 6
Joined: Sat Jan 14, 2006 9:38 am

11015 - 05-2 Rendezvous

Post by Peter3109 » Sun Apr 09, 2006 9:05 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Apr 11, 2006 12:40 am

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

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Mon Apr 17, 2006 4:46 pm

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 :) 
Last edited by Niaz on Thu Apr 20, 2006 11:31 am, edited 1 time in total.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Apr 17, 2006 4:59 pm

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)

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Apr 17, 2006 10:44 pm

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
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Thu Apr 20, 2006 11:28 am

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
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

forgotten
New poster
Posts: 1
Joined: Thu May 04, 2006 10:51 am

11015 - 05-2 Rendezvous

Post by forgotten » Thu May 04, 2006 11:02 am

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
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Sat May 06, 2006 3:57 am

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

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Jun 18, 2006 9:14 am

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 ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 18, 2006 9:42 am

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

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

11015 - 05-2 Rendezvous

Post by shihabrc » Wed Jul 19, 2006 8:57 pm

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

Last edited by shihabrc on Thu Jul 20, 2006 8:17 pm, edited 1 time in total.
Shihab
CSE,BUET

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Jul 20, 2006 7:27 am

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Thu Jul 20, 2006 8:14 pm

Thanx 4 ur hlp. Got AC now.

I really forgot 2 remove my ID frm the code. :oops:
Shihab
CSE,BUET

User avatar
tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

help me

Post by tuman » Sat Jul 22, 2006 9:50 pm

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
Last edited by tuman on Wed Jul 26, 2006 6:45 pm, edited 2 times in total.
We the dreamer of the dreamy dream...

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: help me

Post by Martin Macko » Sun Jul 23, 2006 6:42 pm

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;
}

Post Reply

Return to “Volume 110 (11000-11099)”