11284 - Shopping Trip

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

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

[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

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.

[Darko]

Your output is right. Note that the input is not valid, values are guaranteed to have two digits after the decimal point.

[baodog]

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

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

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

[ayon]

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

[Jan]

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.

[Darko]

You forgot to comment out the freopen line.

Jan, sorry, I removed your otherwise AC code.

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

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

[Jan]

What to do now? Should I report it in Bugs and suggestions?

[windows2k]

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

[SRX]

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)