P8345 「Wdoi-6」华胥之梦

[](https://thwiki.cc/%E4%B8%9C%E6%96%B9%E6%B1%82%E9%97%BB%E5%8F%B2%E7%BA%AA/%E4%BE%BF%E7%AC%BA)

### 简要题意 给定长度为 $n$ 的序列 $a$ 和常数 $c$。构造点数为 $n$ 的有向完全图 $G$ 使得边 $i\to j$（$i\neq j$）的长度为 $a_i-2a_j+c$，保证所有边权**非负**。 接下来给出 $q$ 次询问，每次给出一个点集，试找出图 $G$ 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。 --- ### 原始题意 梅莉做了一个梦，梦到自己穿越到了幻想乡的迷途竹林之中。醒来之后，她希望能够和莲子一起再次穿越境界，进入幻想乡。 但是，这一次，她看到了 $n$ 个世界，其中，第 $i$ 个世界的结界强度为 $a_i$。而世界之间**两两都有**通道相连，莲子和梅莉便是通过这些通道来进行世界之间的穿梭的。 为了避免错过幻想乡所在的世界，因此她们每到达一个世界，都会穿越结界。莲子和梅莉从第 $i$ 个世界中，通过一条通道，再穿越结界进入第 $j$ 个世界，需要使用的灵能为 $a_i-2a_j+c$（保证所需消耗的灵能非负），其中 $c$ 是一个常数，是梅莉每次穿越结界需要的额外灵能消耗。注意，这也意味着，从第 $i$ 个世界到第 $j$ 个世界，与第 $j$ 个世界穿越到第 $i$ 个世界所消耗的灵能，**可能是不同的**。 为了能够高效地找到幻想乡，她们会对你进行 $q$ 次询问，每次询问的时候会给出一个**集合**，表示她们想要进入的世界。由于世界众多，她们希望能够节省灵能，因此她希望你能求出所有包含这些世界的简单路径（即：同一条世界间的通道不会被走多次）中，消耗灵能值之和最少的路径。你只需告诉她们消耗灵能值之和最少为多少。

无

无

### 样例解释 #### 样例 \#1  每两个点之间的边权如图所示。为了便于选手观察，边权的颜色与它所对应的边的颜色相同。 对于第一个询问，可以找到路径 $4\to 1$ ；对于第二个询问，可以找到路径 $3\to 2\to 1$；对于第三个询问，可以找到路径 $2\to 4 \to 1\to 5$。可以证明，这三个方案分别是对应询问的最优方案。 #### 样例 \#2 该样例符合 $\textbf{Subtask 1}$ 的限制。 ### 数据范围 **本题采用捆绑测试。** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \bm{q\le} & \bm{\sum |S|\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline 1 & 30 & 10 & 10 & 10 & - &-\cr\hline 2 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{A}&- \cr\hline 3 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{B}&- \cr\hline 4 & 30 & 10^6 & 10^6 & 10^6& -&1,2,3 \cr\hline \end{array} $$ - 特殊性质 $\bf A$：$a_i$ 单调递增。 - 特殊性质 $\bf B$：$a_i$ 全部相等。 对于 $100\%$ 的数据，保证 $1 \leq S_i \leq n \leq 10^6, 1\leq \sum |S|,q \leq 10^6, 1 \le a_i,c \le 10^9$。