Problem on Spoj problem (INGRED

Revision en1, by hiddentesla, 2016-07-21 18:20:51

problem link: http://www.spoj.com/problems/INGRED/ my code: https://ideone.com/H30OGG

so im having troubles with this problem, my approach using dp: first i represent S as a mask, where if the I'th element of mask is on, it means that we have not visited store at city s[i]

firstly run Floyd-Warshall to get all distances between two cities

dp[x][y][mask] = minimum distance needed to get all S ingridients, with person A at city x, person b at city y, and the mask

if person A lives in city A, person B lives in city B, and there are SS ingridients, the answer is dp[A][B][(2^SS) — 1];

x= position of person A, y= position of person B, dist = distance so far

then i just check for each bit that is on in the mask, assign person A or person B to get it..

but i got WA... cant seem to find where i did wrong. any help?

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 hiddentesla 2016-07-21 18:20:51 936 Initial revision (published)