翻译
查看原帖
翻译
637410
sqrt404楼主2024/3/20 12:49

小A想要给他的朋友小B发送了一条有 mm 个单词的消息。他们的语言由编号从 a1a_1 到 ana_n 的 nn 个单词组成。一些单词具有相同的意思,因此存在 kk 个单词组,其中每个组中的所有单词具有相同的意思。小A知道第 ii 个单词可以以成本 mim_i 发送。

对于他的每个消息中的单词,小A可以将其替换为具有相同意思的另一个单词,或者保持不变。请帮助小A确定发送消息的最小价值。

发送消息的成本是其中每个单词的发送成本的总和。

输入格式

输入的第一行包含三个整数 nn、kk 和 mm(1≤k≤n,m≤1051\le k\le n,m\le 10^5) —— 它们的语言中的单词数量、单词组数量以及小A的消息中的单词数量。

第二行包含 nn 个字符串,由小写英文字母组成,长度不超过 2020,表示这些单词。保证这些单词是不同的。

第三行包含 nn 个整数 a1,a2,⋅⋅⋅⋅⋅⋅,ana_1,a_2,······,a_n (1≤ai≤1091\le a_i\le 10^9),其中 aia_i 表示发送第 ii 个单词的成本。

接下来的 kk 行描述了具有相同含义的单词组。下面的 kk 行中,每行以整数 xx (1≤x≤n1\le x\le n)开头,表示此组中有 xx 个单词,然后是 xx 个整数,表示此组中的单词的索引。保证每个单词只出现在一个组中。

接下来的一行包含 mm 个以空格分隔的单词,表示小A的消息。这些单词中的每个都出现在语言单词列表中。

输出格式

唯一的一行包含在将小A句子中的单词替换为具有相同意义的单词后发送消息的最低成本。

translete by sqrt404

markdown:

小A想要给他的朋友小B发送了一条有 $m$ 个单词的消息。他们的语言由编号从 $a_1$ 到 $a_n$ 的 $n$ 个单词组成。一些单词具有相同的意思,因此存在 $k$ 个单词组,其中每个组中的所有单词具有相同的意思。小A知道第 $i$ 个单词可以以成本 $m_i$ 发送。

对于他的每个消息中的单词,小A可以将其替换为具有相同意思的另一个单词,或者保持不变。请帮助小A确定发送消息的最小价值。

发送消息的成本是其中每个单词的发送成本的总和。
#### 输入格式

输入的第一行包含三个整数 $n$、$k$ 和 $m$($1\le k\le n,m\le 10^5$) —— 它们的语言中的单词数量、单词组数量以及小A的消息中的单词数量。

第二行包含 $n$ 个字符串,由小写英文字母组成,长度不超过 $20$,表示这些单词。保证这些单词是不同的。

第三行包含 $n$ 个整数 $a_1,a_2,······,a_n$ ($1\le a_i\le 10^9$),其中 $a_i$ 表示发送第 $i$ 个单词的成本。

接下来的 $k$ 行描述了具有相同含义的单词组。下面的 $k$ 行中,每行以整数 $x$ ($1\le x\le n$)开头,表示此组中有  $x$ 个单词,然后是 $x$ 个整数,表示此组中的单词的索引。保证每个单词只出现在一个组中。

接下来的一行包含 $m$ 个以空格分隔的单词,表示小A的消息。这些单词中的每个都出现在语言单词列表中。
#### 输出格式
唯一的一行包含在将小A句子中的单词替换为具有相同意义的单词后发送消息的最低成本。

###### translete by [sqrt404](https://www.luogu.com.cn/user/637410)
2024/3/20 12:49
加载中...