## 11284 - Shopping Trip

Moderator: Board moderators

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### 11284 - Shopping Trip

i use floyd to calculate distance between each store
and build a new graph that contains only store node and home node
then I use a bit DP to find the max profit

is this algorithm wrong?

can someone give me some test data ?

btw, what is the range of the cost of road and money saved in stoer? could it be very large?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
That's what I did. But I got WA for using doubles, and got AC by just modifying my code to work only with integers.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I am getting WA. My idea is almost similar and I am using only integers. Here are some cases..

Input:

Code: Select all

``````3

4 5
0 1 1
1 2 3.00
0 3 1.00
3 2 1.50
3 4 3.25
3
1 1.50
1 7.00
2 9.00

4 5
0 1 1
1 2 3.00
0 3 1.00
3 2 1.50
3 4 3.25
4
1 1.50
2 7.00
3 9.00
4 11.00

5 6
0 1 1
1 2 3.00
0 3 1.00
3 2 11.50
3 4 3.25
4 5 8
4
3 1.50
3 7.00
4 1.00
5 20``````
Output:

Code: Select all

``````Daniel can save \$11.00
Daniel can save \$15.50
Daniel can save \$6.50``````
Are these correct? Can anyone post some more cases? Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Your output is right. Note that the input is not valid, values are guaranteed to have two digits after the decimal point.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### more datasets ....

More datasets is really appreciated.
Does the (sum of prices)*100 fit inside
a 32 bit integer? Are all prices positive?
Thanks.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The prices are positive, and everything fits in 32bit signed integer.
Remember to output don't leave the house if the lowest cost is 0.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
100*(sum) more than comfortably fits into 32-bit integer.
Costs are non-negative.

There is one more thing that might cause WA, it is a small implementation detail, read the problem statement carefully.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Darko wrote: There is one more thing that might cause WA, it is a small implementation detail, read the problem statement carefully.
thanks for the hint , after getting too many wa in contest and online-judge, while reading the description again, i thought about multiple edges between two nodes. after checking that it got accepted. unfortuantely i assumed that there will be no multiple edges
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Well, my code handles duplicate edges. And I have tried many cases, but couldnt find the error. So, I am posting my code.

Code: Select all

``code removed by Darko``
Can anyone show where it fails? Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
You forgot to comment out the freopen line.

Jan, sorry, I removed your otherwise AC code.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
No no, I removed the freopen before submitting. But got WA. I submitted it and got WA again. Would you please submit it? Thanks. [If you dont have the code I will PM it, just inform me]
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Very interesting - I checked it against the judge's input and it produces correct answer. But it gets WA on OJ. My compiler is 3.4.6, I am not sure why it would matter.

Maybe it's some C++ thing, maybe you want to repost your code, sorry again for removing it.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
What to do now? Should I report it in Bugs and suggestions?
Ami ekhono shopno dekhi...
HomePage

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Jan wrote:What to do now? Should I report it in Bugs and suggestions?
I get WA all the tiime.
And I passed the input/output above.
Could someone give more tricky input/output?

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
windows2k wrote:
Jan wrote:What to do now? Should I report it in Bugs and suggestions?
I get WA all the tiime.
And I passed the input/output above.
Could someone give more tricky input/output?