PROBLEM LINK:
Author: Utkarsh Saxena
Tester: Alexey Zayakin
Editorialist: Utkarsh Saxena
PROBLEM
You are given a graph of V nodes and E weighted edges, a source node S, destination node F and a special set of N nodes. You are given a value T_i for each special node. For each subset of special nodes find the minimum cost of path from S to T covering all the nodes in the subset.
Cost(path) = Length(path) + \big(\prod_{\text{special node in path}}{T_i}\big)\space mod\space 10^9+7
Constraints: n \le 16, V \le 1000, E \le 3000.
PREREQUISITES
EXPLANATION
Notice that the cost of path is affected by the set of special nodes that lie on it.
Given a set of special nodes to cover \big\{S_0, S_1,.., S_k\big\}. A path that covers these nodes will start from S, cover all the given special nodes, cover some extra special node and then end at F. Let the extra special nodes covered = \big\{S_{e0}, S_{e1},.., S_{eg}\big\}.
Cost(path) = Length(path) + \big(T_0 * T_1 *.. * T_k * T_{e0} * T_{e1} *..* T_{eg} \big)\space mod\space 10^9+7.
So the cost is also dependent on the extra special nodes that you cover apart from the required nodes.
Simpler problem
Let’s assume that we are not allowed to visit any extra special node apart from the given subset of special nodes. For this it is sufficient to minimize the length of the path required in order to minimize the cost of path since the \prod part of cost is constant for this subset.
To solve this problem find SP_{ij} = Shortest path from special node i to special node j that does not include any other special node. For each subset of special node: using this matrix you can calculate the shortest path covering exactly those special nodes.
Denote dp[mask][i] = Length of shortest path that starts from S, ends at special node i and covers exactly those special nodes denoted by the ON bits of mask.
In order to end at this state, previous state can be
- We have visited all nodes in mask and are currently at j^{th} node.
- We have visited all nodes in mask except i and are currently at j^{th} node.
dp[mask][i] = min(dp[mask\oplus 2^i][j]\space + sp[j][i],\space dp[mask][j]\space + sp[j][i]) where j is present in mask.
Notice that this recurrence contains a cyclic dependency. We can solve this recurrence using Dijsktra shortest path algorithm on the graph made by the transitions of above recurrence.
Denote dp2[mask] = min(dp[mask][i] + sp[i][F]) + prod[mask]. This will denote the minimum cost of path that begins at S, ends at F and covers only the special nodes mentioned in mask.
Here prod[mask] = product of T_i of all i present in mask.
Final solution
For the actual solution we need to allow extra special nodes to be added to the given subset of nodes. Assume we want to find the answer for subset denoted by mask We will add some extra special nodes to this set to make the cost better. Denote this new set of special nodes made after adding extra nodes = Opmask. Notice that the set denoted by mask is always a subet of set denoted by Opmask. The cost of covering Opmask is dp2[Opmask].
Thus we can iterate over all possible Opmask that has mask as a subset to get the best answer.
Answer for mask = min(dp2[opmask]) where opmask \& mask=mask. This can be efficiently calculated using the technique mentioned in suboptimal solution of this blog.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.