Page 1 of 3
11284 - Shopping Trip
Posted: Sun Sep 16, 2007 5:45 am
by ziliang
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?
Posted: Sun Sep 16, 2007 6:30 am
by sclo
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.
Posted: Sun Sep 16, 2007 8:44 pm
by Jan
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
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.
Posted: Sun Sep 16, 2007 10:17 pm
by Darko
Your output is right. Note that the input is not valid, values are guaranteed to have two digits after the decimal point.
more datasets ....
Posted: Sun Sep 16, 2007 11:53 pm
by baodog
More datasets is really appreciated.
Does the (sum of prices)*100 fit inside
a 32 bit integer? Are all prices positive?
Thanks.
Posted: Mon Sep 17, 2007 12:21 am
by sclo
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.
Posted: Mon Sep 17, 2007 12:34 am
by Darko
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.
Posted: Mon Sep 17, 2007 1:05 am
by ayon
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
Posted: Mon Sep 17, 2007 2:44 am
by Jan
Well, my code handles duplicate edges. And I have tried many cases, but couldnt find the error. So, I am posting my code.
Can anyone show where it fails? Thanks in advance.
Posted: Mon Sep 17, 2007 4:47 am
by Darko
You forgot to comment out the freopen line.
Jan, sorry, I removed your otherwise AC code.
Posted: Mon Sep 17, 2007 6:27 am
by Jan
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]
Posted: Mon Sep 17, 2007 7:04 am
by Darko
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.
Posted: Mon Sep 17, 2007 8:27 am
by Jan
What to do now? Should I report it in Bugs and suggestions?
Posted: Sun Sep 23, 2007 4:54 am
by windows2k
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?
Thanks in advance
Posted: Mon Sep 24, 2007 6:59 pm
by SRX
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?
Thanks in advance
Edited.
I found my error :
I forgot to add eps when I change all double to int. (*100)