{"problem":{"name":"「Wdoi-6」华胥之梦","description":{"content":"### 简要题意 给定长度为 $n$ 的序列 $a$ 和常数 $c$。构造点数为 $n$ 的有向完全图 $G$ 使得边 $i\\to j$（$i\\neq j$）的长度为 $a_i-2a_j+c$，保证所有边权**非负**。 接下来给出 $q$ 次询问，每次给出一个点集，试找出图 $G$ 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。 --- ### 原始题意 梅莉做了一个梦，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8345"},"statements":[{"statement_type":"Markdown","content":"### 简要题意\n\n给定长度为 $n$ 的序列 $a$ 和常数 $c$。构造点数为 $n$ 的有向完全图 $G$ 使得边 $i\\to j$（$i\\neq j$）的长度为 $a_i-2a_j+c$，保证所有边权**非负**。\n\n接下来给出 $q$ 次询问，每次给出一个点集，试找出图 $G$ 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。\n\n---\n### 原始题意\n\n梅莉做了一个梦，梦到自己穿越到了幻想乡的迷途竹林之中。醒来之后，她希望能够和莲子一起再次穿越境界，进入幻想乡。\n\n但是，这一次，她看到了 $n$ 个世界，其中，第 $i$ 个世界的结界强度为 $a_i$。而世界之间**两两都有**通道相连，莲子和梅莉便是通过这些通道来进行世界之间的穿梭的。\n\n为了避免错过幻想乡所在的世界，因此她们每到达一个世界，都会穿越结界。莲子和梅莉从第 $i$ 个世界中，通过一条通道，再穿越结界进入第 $j$ 个世界，需要使用的灵能为 $a_i-2a_j+c$（保证所需消耗的灵能非负），其中 $c$ 是一个常数，是梅莉每次穿越结界需要的额外灵能消耗。注意，这也意味着，从第 $i$ 个世界到第 $j$ 个世界，与第 $j$ 个世界穿越到第 $i$ 个世界所消耗的灵能，**可能是不同的**。\n\n为了能够高效地找到幻想乡，她们会对你进行 $q$ 次询问，每次询问的时候会给出一个**集合**，表示她们想要进入的世界。由于世界众多，她们希望能够节省灵能，因此她希望你能求出所有包含这些世界的简单路径（即：同一条世界间的通道不会被走多次）中，消耗灵能值之和最少的路径。你只需告诉她们消耗灵能值之和最少为多少。\n\n## Input\n\n- 第一行三个整数 $n,c,q$。\n- 第二行 $n$ 个整数表示数列 $a$。\n- 接下来 $q$ 行。每行第一个整数 $|S|$，即集合 $S$ 的大小。后面 $|S|$ 个互不相同的整数表示集合 $S$。\n\n## Output\n\n- 输出共 $q$ 行，每行一个整数，表示询问的答案。\n\n[samples]\n\n## Background\n\n[![](https://cdn.luogu.com.cn/upload/image_hosting/lkvzvoj9.png)](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\n## Note\n\n### 样例解释\n\n#### 样例 \\#1\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/x3r2ucsl.png)\n\n每两个点之间的边权如图所示。为了便于选手观察，边权的颜色与它所对应的边的颜色相同。\n\n对于第一个询问，可以找到路径 $4\\to 1$\n；对于第二个询问，可以找到路径 $3\\to 2\\to 1$；对于第三个询问，可以找到路径 $2\\to 4 \\to 1\\to 5$。可以证明，这三个方案分别是对应询问的最优方案。\n#### 样例 \\#2\n\n该样例符合 $\\textbf{Subtask 1}$ 的限制。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\textbf{\\textsf{分值}} & \\bm{n\\le } & \\bm{q\\le} & \\bm{\\sum |S|\\le} & \\textbf{\\textsf{特殊性质}}&\\textbf{Subtask \\textsf{依赖}}\\cr\\hline\n1 & 30 & 10 & 10 & 10 & - &-\\cr\\hline\n2 & 20 & 10^5 & 10^5 & 10^5 & \\mathbf{A}&- \\cr\\hline\n3 & 20 & 10^5 & 10^5 & 10^5 & \\mathbf{B}&-  \\cr\\hline\n4 & 30 & 10^6 & 10^6 &  10^6& -&1,2,3 \\cr\\hline\n\\end{array}\n$$\n\n- 特殊性质 $\\bf A$：$a_i$ 单调递增。\n- 特殊性质 $\\bf B$：$a_i$ 全部相等。\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8345","tags":["贪心","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5 20 3\n7 4 2 5 9\n2 1 4\n3 1 2 3\n4 1 4 2 5","11\n24\n34"],["10 928698067 3\n331485039 15480787 61584781 252174726 472089427 95998831 252561792 118119945 315548522 24453837\n4 9 1 10 2\n5 10 6 1 5 8\n1 5\n","1798602551\n2249463436\n0\n"]],"created_at":"2026-03-03 11:09:25"}}