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
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
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 -
fn(1<<i,i) + dist[b][src[i]] + dist[src[i]][dest[i]] for all values of i)
Overall time complexity would be
n is the number of entries in the src array.