Problem on Spoj problem (INGRED

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

problem link: my code:

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

so i made recursive function solve(x,y,mask,dist)

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?

Tags spoj, dp, bitmasks


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