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;
}
更多推荐
Nastya and Potions【DFS】
发布评论