若是使用法术攻击虽然好彻底将一个怪兽杀死。而利用法术攻击虽然可以彻底以一个怪兽杀死。

3875: [Ahoi2014]骑兵游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

3875: [Ahoi2014]骑兵游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

Description

 【故事背景】

年代久远的宅男生活受到,JYY又打有了同缓RPG游戏。在是戏中JYY会

装扮一个大胆的骑士,用外手中的长剑去杀死入侵村庄的怪兽。

【问题讲述】

每当是戏受,JYY一共有半点种攻击方式,一栽是普通攻击,一栽是法术攻击。两种攻击方式都见面消耗JYY一些体力。采用普通攻击进攻很兽并无可知把死兽彻底杀死,怪兽的尸体可以转换来任何部分新的怪兽,注意一个怪兽可能通过几赖普通攻击后更换回一个或者重复多同的怪兽;而采取法术攻击虽然好彻底将一个怪兽杀死。当然了,一般的话,相比普通攻击,法术攻击会消耗又多之体力值(但由于玩耍系统bug,并无包及时一点)。

游戏世界被一共发N种不同的怪兽,分别由1暨N编号,现在1声泪俱下老兽入侵村庄了,JYY想明白,最少花费稍微体力值才能够将具有村庄中的怪兽全部杀为?

Description

 【故事背景】

年代久远的宅男生活遭,JYY又打有了扳平缓慢RPG游戏。在斯戏中JYY会

扮作一个无畏的骑士,用他手中的长剑去杀死入侵村庄的怪兽。

【问题讲述】

以斯戏被,JYY一共有有限栽攻击方式,一种植是普通攻击,一种是法术攻击。两种植攻击方式都见面消耗JYY一些体力。采用普通攻击进攻大兽并无能够将那个兽彻底杀死,怪兽的遗骸可以变换来另部分新的怪兽,注意一个怪兽可能通过几涂鸦普通攻击后转移扭一个或者另行多一致的怪兽;而利用法术攻击虽然可彻底以一个怪兽杀死。当然了,一般的话,相比普通攻击,法术攻击会消耗又多之体力值(但鉴于玩耍系统bug,并无保证及时一点)。

打世界被总计发生N种不同之怪兽,分别由1届N编号,现在1如泣如诉特别兽入侵村庄了,JYY想明白,最少花费多少体力值才能够以有所村庄被之怪兽全部结果为?

Input

先是尽包含一个平头N。

对接下去N行,每行描述一个怪兽之信;

里头第i实施包含几个整数,前三单整数为Si,Ki和Ri,表示于i号怪兽,

普通攻击需要消耗Si的体力,法术攻击需要吃Ki的体力,同时i号怪兽死亡后会发Ri个新的怪兽。表示一个初面世的怪兽编号。同一编号的怪兽可以起多独。

Input

先是推行包含一个整数N。

属下N行,每行描述一个怪兽的信息;

内第i执包含几独整数,前三个整数为Si,Ki和Ri,表示对i号怪兽,

普通攻击需要消耗Si的体力,法术攻击需要吃Ki的体力,同时i号怪兽死亡后会见时有发生Ri个新的怪兽。表示一个新面世的怪兽编号。同一编号的怪兽可以起多只。

Output

 输出一行一个平头,表示最少需要的体力值。

Output

 输出一行一个整数,表示最少要之体力值。

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

Sample Output

26

Sample Output

26

HINT

【样例说明】

第一用消耗4点体力用普通攻击,然后起的怪兽编号是2,2与3。

消费10点体力用法术攻击杀死两只号也2底怪兽。

余下3如泣如诉特别兽花费1点体力进行普通攻击。

此刻庄里之怪兽编号是2以及4。

终极花11点体力用法术攻击将这点儿独特别兽彻底杀死。

总计消费的体力是4+5+5+1+5+6=26。

【数据范围】

2<=N<=2*10^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=5*10^14

 

 

  这真的是一样鸣特别妙的修,反正自己是没有做出来的。

  困扰在”一个老大被斩死会助长生同积聚不同之不得了”这个问题达到,难道怪物基因都是一样之怎么跑不过缺少路程啊。

  去网上看了一样波题解发现都称的酷少,似乎是为及时题太次?智障选手要过早弃疗。

  假设没有环出现,对它是一个DAG,就是一个格外水之DP题了,反向拓扑一下。

  然后现在生环了。有环就见面时有发生什么为?有后效性。DP是匪能够解决发生后效性的题目的。

  但是SPFA可以。SPFA就是了无任由后效性的算法(所以非常爱让轧?)。

  设将大净化掉的极小花费是f。那么就发生:
f[i]=min(K[i],S[i]+Σf[R]);

  所以一个械给更新可能会见促成前驱的换代。

  所以把她的先辈扔上队直到队列为空输出f[1]大凡呀算法啊什么什么什么!

  咳咳。所以实际贯彻步骤就是是如此:

  将装有的点的f赋为K[i]连投入队列。

  计算队首底f’。如果比较当下良,就更新并加入所有前任。

  直到队列空。

  其实我充分害怕是事物的复杂度,但是就算是了了…

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 200010;
const int M = 1000010;
struct Node{int to,next;}E[M];
int head[N],tot,n,In[N],R[N];
LL S[N],f[N],K[N];
vector<int>G[N];

int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void SPFA()
{
  queue<int>Q;for(int i=1;i<=n;++i)Q.push(In[i]=i);
  while(!Q.empty()){
    int x=Q.front();Q.pop();In[x]=0;LL sum=S[x];
    for(int i=0;i<R[x];++i)sum+=f[G[x][i]];
    if(sum>=f[x])continue;f[x]=sum;
    for(int e=head[x];e;e=E[e].next)
      if(!In[E[e].to])Q.push(E[e].to),In[E[e].to]=1;
  }
}

int main()
{
  n=gi();
  for(int i=1;i<=n;++i){
    S[i]=gL();K[i]=gL();R[i]=gi();
    for(int j=1;j<=R[i];++j){
      int r=gi();
      link(r,i);G[i].push_back(r);
    }
    f[i]=K[i];
  }
  SPFA();
  printf("%lld\n",f[1]);
  return 0;
}

  

HINT

【样例说明】

先是用消耗4点体力用普通攻击,然后出现的怪兽编号是2,2暨3。

费10沾体力用法术攻击杀死两个号为2之怪兽。

剩余3哀号颇兽花费1点体力进行普通攻击。

这庄里之怪兽编号是2跟4。

最终花11点体力用法术攻击将随即简单单怪兽彻底杀死。

一起消费的体力是4+5+5+1+5+6=26。

【数据范围】

2<=N<=2*10^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=5*10^14

 

 

  这确实是千篇一律志大理想的题,反正自己是没开出来的。

  困扰在”一个老大被砍伐死会添加出一致堆放不同的不胜”这个题材达成,难道怪物基因都是一样的怎么跑不过差里程啊。

  去网上看了同波题解发现都提的不行少,似乎是为及时题太次?智障选手要过早弃疗。

  假设没有环出现,对其是一个DAG,就是一个良水之DP题了,反向拓扑一下。

  然后现在发环了。有环就会来啊也?有后效性。DP是勿能够解决发生后效性的题材之。

  但是SPFA可以。SPFA就是全没任由后效性的算法(所以老容易给轧?)。

  设将生净化掉的极其小花费是f。那么即便有:
f[i]=min(K[i],S[i]+Σf[R]);

  所以一个军械给更新可能会见造成前驱的创新。

  所以把其的先驱扔上队直到队列为空输出f[1]是什么算法啊什么什么什么!

  咳咳。所以实际落实步骤就是是这般:

  将装有的点的f赋为K[i]连进入队列。

  计算队首的f’。如果比当下完美,就创新并在所有前任。

  直到队列空。

  其实我挺怕是事物的复杂度,但是就是是喽了…

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 200010;
const int M = 1000010;
struct Node{int to,next;}E[M];
int head[N],tot,n,In[N],R[N];
LL S[N],f[N],K[N];
vector<int>G[N];

int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void SPFA()
{
  queue<int>Q;for(int i=1;i<=n;++i)Q.push(In[i]=i);
  while(!Q.empty()){
    int x=Q.front();Q.pop();In[x]=0;LL sum=S[x];
    for(int i=0;i<R[x];++i)sum+=f[G[x][i]];
    if(sum>=f[x])continue;f[x]=sum;
    for(int e=head[x];e;e=E[e].next)
      if(!In[E[e].to])Q.push(E[e].to),In[E[e].to]=1;
  }
}

int main()
{
  n=gi();
  for(int i=1;i<=n;++i){
    S[i]=gL();K[i]=gL();R[i]=gi();
    for(int j=1;j<=R[i];++j){
      int r=gi();
      link(r,i);G[i].push_back(r);
    }
    f[i]=K[i];
  }
  SPFA();
  printf("%lld\n",f[1]);
  return 0;
}

  

相关文章