Nastya and Potions【DFS】

Nastya and Potions【DFS】"/>

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 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL c[N],w[N];
vector<int> v[N];
LL dfs(int u)
{if(w[u]!=-1) return w[u];if(v[u].size()==0) return c[u];LL sum=0;for(int i=0;i<v[u].size();i++){if(c[v[u][i]])sum+=dfs(v[u][i]);}return w[u]=min(sum,c[u]);
}
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) v[i].clear(),w[i]=-1;for(int i=1;i<=n;i++) cin>>c[i];while(k--){int x;cin>>x;c[x]=0;}for(int i=1;i<=n;i++){int m;scanf("%d",&m);while(m--){int x;cin>>x;v[i].push_back(x);}}for(int i=1;i<=n;i++){printf("%lld ",dfs(i)); }printf("\n");}return 0;
}