动态模板网站建设全国疫情最新报告
炼金术士纳斯蒂亚喜欢混合药剂。一共有n种药剂，ci硬币可以买到一种 i 型药剂。 任何一种药剂都只能通过一种方式获得，即混合其他几种药剂。混合过程中使用的药剂将被消耗掉。此外，任何药剂都不能通过一个或多个混合过程从自身获得。
作为一名经验丰富的炼金术士，Nastya拥有无限量的k种药剂p1、p2、…、pk，但她不知道下一步要获得哪一种。为了做出决定，她要求你为每1≤i≤n找到她下一次获得 i 型药剂所需的最低硬币数量。
输入：
每个测试的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。每个测试用例描述如下：
第一行包含两个整数n和k（1≤k＜n≤2‧10^5）——药剂类型的总数和Nastya已经拥有的药剂类型的数量。
第二行包含n个整数c1、c2、…、cn（1≤ci≤10^9）——购买药剂的成本。
第三行包含k个不同的整数p1，p2，…，pk（1≤pi≤n）——药剂的指数Nastya已经有了无限的供应。
接下来是描述通过混合获得药剂的方法的n行。每行以整数mi（0≤mi＜n）开始——混合类型 i（1≤i≤n）的药剂所需的药剂数量。然后这行包含mi不同的整数e1、e2、…、emi（1≤ej≤n ，ej≠i）——混合Ⅱ型药剂所需的药剂指数。如果此列表为空，则只能购买类型为 i 的药剂。保证不会通过一个或多个混合过程从自身获得任何药剂。保证所有测试用例的所有nn值之和不超过2∙10^5。同样，保证所有测试用例中所有mi值的总和不超过2∙10^5。
输出：
对于每个测试用例，输出n个整数——Nastya获得每种类型的药剂所需花费的最小硬币数。
输入样例：
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
输出样例
23 8 0 5 10 0 143 0 5 0 1 3 4 0 0 0 0
输入样例：
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
输出样例：
0 0 0 0 0 2 0 0 0 0 0 0 0 0
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e5+10;
long long dp[N];
long long c[N];
vector<int>v[N];
int dfs(int x)
{if(dp[x]!=-1) return dp[x];if(v[x].size()==0){dp[x]=c[x];return dp[x];}long long sum=0;for(int i=0;i<v[x].size();i++){sum+=dfs(v[x][i]);}dp[x]=min(sum,c[x]);return dp[x];
}
int main()
{int t;cin>>t;while(t--){int n,k;cin>>n>>k;memset(dp,-1,sizeof dp);for(int i=1;i<=n;i++){cin>>c[i];v[i].clear();}for(int i=1;i<=k;i++){int x;cin>>x;c[x]=0;}for(int i=1;i<=n;i++){int num;cin>>num;for(int j=1;j<=num;j++){int x;cin>>x;v[i].push_back(x);}}for(int i=1;i<=n;i++) cout<<dfs(i)<<" ";cout<<endl;}return 0;
}