#2021. 「Wdoi-6」华胥之梦

「Wdoi-6」华胥之梦

题目描述

简要题意

给定长度为 nn 的序列 aa 和常数 cc。构造点数为 nn 的有向完全图 GG 使得边 i→ji\to j(i≠ji\neq j)的长度为 ai−2aj+ca_i-2a_j+c,保证所有边权非负。

接下来给出 qq 次询问,每次给出一个点集,试找出图 GG 的一条最短的简单路径,满足其经过点集中所有点,并输出它的长度。


原始题意

梅莉做了一个梦,梦到自己穿越到了幻想乡的迷途竹林之中。醒来之后,她希望能够和莲子一起再次穿越境界,进入幻想乡。

但是,这一次,她看到了 nn 个世界,其中,第 ii 个世界的结界强度为 aia_i。而世界之间两两都有通道相连,莲子和梅莉便是通过这些通道来进行世界之间的穿梭的。

为了避免错过幻想乡所在的世界,因此她们每到达一个世界,都会穿越结界。莲子和梅莉从第 ii 个世界中,通过一条通道,再穿越结界进入第 jj 个世界,需要使用的灵能为 ai−2aj+ca_i-2a_j+c(保证所需消耗的灵能非负),其中 cc 是一个常数,是梅莉每次穿越结界需要的额外灵能消耗。注意,这也意味着,从第 ii 个世界到第 jj 个世界,与第 jj 个世界穿越到第 ii 个世界所消耗的灵能,可能是不同的。

为了能够高效地找到幻想乡,她们会对你进行 qq 次询问,每次询问的时候会给出一个集合,表示她们想要进入的世界。由于世界众多,她们希望能够节省灵能,因此她希望你能求出所有包含这些世界的简单路径(即:同一条世界间的通道不会被走多次)中,消耗灵能值之和最少的路径。你只需告诉她们消耗灵能值之和最少为多少。

输入格式

  • 第一行三个整数 n,c,qn,c,q。
  • 第二行 nn 个整数表示数列 aa。
  • 接下来 qq 行。每行第一个整数 ∣S∣|S|,即集合 SS 的大小。后面 ∣S∣|S| 个互不相同的整数表示集合 SS。

输出格式

  • 输出共 qq 行,每行一个整数,表示询问的答案。

    样例

5 20 3
7 4 2 5 9
2 1 4
3 1 2 3
4 1 4 2 5
11
24
34
10 928698067 3
331485039 15480787 61584781 252174726 472089427 95998831 252561792 118119945 315548522 24453837
4 9 1 10 2
5 10 6 1 5 8
1 5
1798602551
2249463436
0

题目来源:洛谷 P8345