I am unable to solve the problem SPOJ.com - Problem 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.