I regard it as a graph theory problem,and solve it in O(M*2^N).
  But it is very slow,so I would like to hear some others' algorithm.Maybe we can make progress together.
  Contact me: yym2008@hotmail.com

Just get only bottles he wants (ignore others). Perform mix-up by bit-wise OR (I think you did it). And use heap for Dijkstra - it works very well because |E| < |V|

thanks Denis Koshman, first i Time limit exceeded in test 11, when i use your hint i AC in 0.453 s, i dont forgot your hint in all my life :D.

GOOD LUCK!!!

How can I regard it as a graph theory problem??? What do edges mean and what do vertex mean?

Edited by author 17.05.2012 18:31

ive got the same problem my solutions (both using function w/ memoization and precomputing all the possible bitmasks before answering) pass the time limits but are 6-7 times slower :|