I am unable to solve the problem http://www.spoj.com/problems/COURIER/ please help me how to solve this problem . I have seen a solution but not able to get the logic. Please help me out

The courier guy has to start from a particular node, and for each delivery, he has to start from a node and reach another node. He can choose any arbitrary order to perform the deliveries.

Let each delivery be denoted by `src[i]`

and `dest[i]`

. (Multiple deliveries to the same pair of cities are stored separately). Since the courier guy can take only one package at a time, we can assume that the guy always moves to the `dest[i]`

when he picks an `src[i]`

. This boils down to a slightly modified version of Travelling Salesman Problem. We define the DP state as follows:

`fn(mask, prev) = min( fn(set kth bit in mask, k) + dist[dest[prev]][src[k]] + dist[src[k]][dest[k]] ) for every k not in mask`

Here `mask`

denotes the set of deliveries that have been completed and `prev`

is the index(from src[]/dest[] arrays) of the last delivery that has been completed. `dist[x][y]`

represents the shortest distance between the nodes x & y. This can be found using Floyd Warshal algorithm.

The answer is found by iterating over all possible starting masks plus the distance from the starting city -

min(

`fn(1<<i,i) + dist[b][src[i]] + dist[src[i]][dest[i]] for all values of i)`

Overall time complexity would be `O(n*n*(2^n))`

where `n`

is the number of entries in the src[] array.