AT_abc395_g [ABC395G] Minimum Steiner Tree 2

给定正整数 $N$ 和 $K$，以及一个 $N \times N$ 的矩阵 $C=(C_{i,j})$（$1 \leq i,j \leq N$）。保证 $C_{i,i}=0$ 且 $C_{i,j}=C_{j,i}$。 存在一个包含 $N$ 个顶点的带权完全图，顶点编号为 $1,2,\ldots,N$。对于满足 $i < j$ 的顶点对 $i,j$，连接顶点 $i$ 和 $j$ 的边的权重为 $C_{i,j}$。 给定 $Q$ 个查询。第 $i$ 个查询给出两个不同的整数 $s_i, t_i$（$K+1 \leq s_i, t_i \leq N$），请对每个查询回答以下问题： > 从该图中移除任意数量的边和顶点后，得到的**连通**子图若包含顶点 $1,2,\ldots,K,s_i,t_i$，则称其为**良构子图**。 > > 良构子图的**成本**定义为子图中所有边的权重之和。 > > 求良构子图的最小成本。

输入通过标准输入给出，格式如下： > $N$ $K$ > $C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,N}$ > $C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,N}$ > $\vdots$ > $C_{N,1}$ $C_{N,2}$ $\dots$ $C_{N,N}$ > $Q$ > $s_1$ $t_1$ > $s_2$ $t_2$ > $\vdots$ > $s_Q$ $t_Q$

输出 $Q$ 行，第 $i$ 行对应第 $i$ 个查询的答案。

### 约束条件 - $3 \leq N \leq 80$ - $1 \leq K \leq \min(N-2, 8)$ - $0 \leq C_{i,j} \leq 10^9$（$1 \leq i,j \leq N$ 且 $i \neq j$） - $C_{i,j} = C_{j,i}$（$1 \leq i,j \leq N$ 且 $i \neq j$） - $C_{i,i} = 0$（$1 \leq i \leq N$） - $1 \leq Q \leq 5000$ - $K+1 \leq s_i, t_i \leq N$（$1 \leq i \leq Q$） - $s_i \neq t_i$（$1 \leq i \leq Q$） - 输入均为整数 ### 样例解释 1 - **第一个查询**：最优方案保留顶点 $1,2,3,4,5$ 和边 $1-4,2-3,3-5,4-5$，成本为 $4$。 - **第二个查询**：最优方案保留顶点 $1,2,3,5$ 和边 $1-5,2-3,3-5$，成本为 $3$。 翻译由 DeepSeek R1 完成