Let’s try a DP like this:

\(dp(X, y) = \) the minimum cost of a Steiner tree that includes nodes in set \(X\), and rooted at node \(y\).

What we want to find for each query is \(dp(\{1,2,...,K,s_i\}, t_i)\).

\(dp(X, y)\) can be calculated as follows:

• If \(X = \emptyset\) or \(X = \{y\}\), then \(dp(X, y) = 0\)
• \(\displaystyle dp(X, y) = \min (\min _ {Z \subset X} dp(Z, y) + dp(X \setminus Z, y), \min _{1 \le i \le N} dp(X, i) + C_{i, y})\)

The two \(\min\) terms represent two possible cases of a nontrivial Steiner tree rooted at node \(y\): either \(y\) has more than one child, in which case it can be split into two Steiner trees for disjoint subsets, or if \(y\) has only one child \(i\), it’s the addition of the edge \((i, y)\) to a Steiner tree with root \(i\).

Note that the latter transition has a cycle, and we need to avoid self-referential transitions. We can do this by fixing \(X\) and doing the left \(\min\) transition first, and then doing the right \(\min\) transition in the style of Dijkstra’s algorithm. Since the graph is dense, we should use the variant that finds the minimum-cost unvisited vertex by linear search, for a total of \(O(N^2)\) time, instead of using a priority queue / heap.

The time complexity of calculating all \(dp(X, *)\) is \(O(3^{|X|} N + 2^{|X|} N^2)\). Since \(X\) ranges over sets obtained by adding at most one element to \(\{1, 2, ..., K\}\), we can solve this problem in \(O(3^K N^2 + 2^K N^3)\) time.

Sample code (PyPy3)