NC20537. [AHOI2014]骑士游戏
描述
输入描述
第一行包含一个整数N。接下来N行，每行描述一个怪兽的信息；其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽，普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
输出描述
输出一行一个整数，表示最少需要的体力值。
示例1
输入:
4 4 27 3 2 3 2 3 5 1 2 1 13 2 4 2 5 6 1 2
输出:
26
说明:
首先用消耗4点体力用普通攻击，然后出现的怪兽编号是2，2和3。花费10点体力用法术攻击杀死两个编号为2的怪兽。剩下3号怪兽花费1点体力进行普通攻击。此时村庄里的怪兽编号是2和4。最后花费11点体力用法术攻击将这两只怪兽彻底杀死。一共花费的体力是4+5+5+1+5+6=26。C++11(clang++ 3.9) 解法, 执行用时: 707ms, 内存消耗: 30456K, 提交时间: 2020-09-23 12:08:55
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
int n;LL a[N],d[N];bool inq[N];
vector<int>to[N],back[N];
queue<int>q;
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<=n;i++){
scanf("%lld%lld%d",&a[i],&d[i],&x);q.push(i);
while(x--)scanf("%d",&y),to[i].pb(y),back[y].pb(i);
}
while(!q.empty()){
int u=q.front();q.pop();inq[u]=false;
LL res=a[u];for(auto x:to[u])res+=d[x];
if(res>=d[u])continue;d[u]=res;
for(auto v:back[u])if(!inq[v])q.push(v),inq[v]=true;
}
printf("%lld\n",d[1]);
return 0;
}