Nastya 与魔法药水

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

现有 $n$ 种药水，第 $i$ 种药水可以用 $c_i$ 个金币买入。每种药水至多有一种合成配方；合成时，所有原料药水会被完全消耗。配方依赖图中不存在环。

Nastya 可以无限制地免费获得 $p_1,p_2,\ldots,p_k$ 这 $k$ 种药水。对于每个 $1\le i\le n$，请分别求出获得一瓶第 $i$ 种药水所需的最少金币数。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据中：

• 第一行包含两个整数 $n,k$；
• 第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$；
• 第三行包含 $k$ 个互不相同的整数 $p_1,p_2,\ldots,p_k$；
• 接下来 $n$ 行描述配方。第 $i$ 行先给出 $m_i$，再给出 $m_i$ 个互不相同的原料编号 $e_1,e_2,\ldots,e_{m_i}$。若 $m_i=0$，则第 $i$ 种药水不能合成，只能购买或免费获得。

输出格式

对于每组测试数据，输出一行 $n$ 个整数，第 $i$ 个整数表示获得一瓶第 $i$ 种药水所需的最少金币数。

样例输入 1

4
5 1
30 8 3 5 10
3
3 2 4 5
0
0
2 3 5
0
3 2
5 143 3
1 3
1 2
0
2 1 2
5 1
5 4 1 3 4
2
2 4 5
3 3 5 4
2 1 4
1 5
0
4 2
1 1 5 4
2 4
3 2 4 3
0
2 2 4
1 2

样例输出 1

23 8 0 5 10
0 143 0
5 0 1 3 4
0 0 0 0

样例输入 2

3
6 3
5 5 4 5 2 2
3 4 5
2 2 5
1 5
3 4 1 6
4 2 6 1 5
0
0
6 2
1 4 4 1 5 2
3 6
4 6 3 4 5
4 6 5 3 4
0
1 5
1 6
0
2 1
4 3
1
0
1 1

样例输出 2

0 0 0 0 0 2
0 0 0 0 0 0
0 0

样例解释

在样例一的第一组数据中，第 $3$ 种药水免费。第 $1$ 种药水用第 $2,4,5$ 种药水合成需要 $8+5+10=23$ 个金币，比直接购买更便宜。第 $4$ 种药水直接购买比用第 $3,5$ 种药水合成更便宜。

数据范围

对于所有数据：

• $1\le t\le 10^4$；
• $1\le k<n\le 2\times10^5$；
• $1\le c_i\le 10^9$；
• $0\le m_i<n$；
• $1\le p_i,e_j\le n$，且 $e_j\ne i$；
• 同一免费药水列表内的编号互不相同，同一配方内的原料编号互不相同；
• 配方依赖图无环；
• 一个输入文件内所有测试数据的 $n$ 之和不超过 $2\times10^5$；
• 一个输入文件内所有 $m_i$ 之和不超过 $2\times10^5$。

各子任务独立计分。

来源与改编说明

本题改编自 Codeforces 1851E - Nastya and Potions。中文表述经过规范化，并增加了独立计分的子任务；题意与原题一致。