I was trying to solve COURIER on spoj . [ Link ]
As the Sum of couriers to be send are only 12 I broke up it into 12 individual orders.
My state : F[i][mask] represents the minimum cost for completing all the couriers in mask with last courier activity completed being i.
Recurrence : F[i][mask] = minimum of ( k belongs to subset denoted by mask F[k][ subset — { i } th courier ] + Cost of going from end of k th courier to beginning of the i th courier + Cost of going from beginning to end ).
Now, My answer will be F[ x ][ all the couriers denotes by 11111... ] + Cost to go from end point of x activity to starting point
Base Case being for all subsets containing only one activity with cost = the cost of going to the end of the courier from starting point through the starting point of the courier.
The Cost for going from some point to other point is calculated via All pair shortest path (Floyd Warshall)
I have been trying it for 8 hours now , and my code doesn't give right output on sample case I don't know why !! Can someone point out the mistake in my method or recurrence or state ??
Just in case if you want to check out if there is some mistake in my code ?
I saw some solutions too online they had a different state but I think my state has every important information for transitions!! Moreover their solutions too had same kind of idea!!
Your initialization of dp[i][j] is wrong in code.
UPD: Guess you've noticed it before me and reinitialized dp[i][j] in cycle.