E. Nastya and Potions（DFS+记忆化搜索）

炼金术士纳斯蒂亚喜欢混合药剂。一共有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;
}