在那一个游戏中JYY会,在那么些游戏中JYY会

3875: [Ahoi2014]骑兵游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

3875: [Ahoi2014]铁骑游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

Description

 【传说背景】

绵绵的宅男子活中,JYY又挖掘出了一款SportagePG游戏。在那几个游戏中JYY会

扮作四个助人为乐的骑士,用她手中的长剑去杀死入侵村庄的怪兽。

【难题讲述】

在那个游乐中,JYY一共有三种攻击格局,1种是普通攻击,1种是法术攻击。两种攻击方式都会消耗JYY壹些体力。采取普通攻击进攻怪兽并无法把怪兽彻底杀死,怪兽的遗骸能够变出其他一些新的怪兽,注意2个怪兽恐怕通过若干次普通攻击后变回三个或越来越多壹致的怪兽;而使用法术攻击则能够彻底将贰个怪兽杀死。当然了,一般的话,比较普通攻击,法术攻击会消耗越来越多的体力值(但出于玩耍系统bug,并不保障这点)。

游戏世界中累计有N种分裂的怪兽,分别由一到N编号,未来1号怪兽入侵村庄了,JYY想知道,最少花费多少年体育力值才能将具有村庄中的怪兽全体干掉呢?

Description

 【旧事背景】

天长日久的宅男子活中,JYY又挖掘出了一款WranglerPG游戏。在那一个娱乐中JYY会

饰演一个胆大的轻骑,用她手中的长剑去杀死侵略村庄的怪兽。

【难题讲述】

在那些娱乐中,JYY壹共有三种攻击方式,1种是普通攻击,1种是法术攻击。三种攻击方式都会消耗JYY一些体力。选择普通攻击进攻怪兽并不能够把怪兽彻底杀死,怪兽的尸体能够变出任何1些新的怪兽,注意2个怪兽大概通过若干次普通攻击后变回2个或越多1致的怪兽;而选用法术攻击则足以彻底将八个怪兽杀死。当然了,一般的话,相比较普通攻击,法术攻击会消耗更加多的体力值(但由于玩耍系统bug,并不有限援救那或多或少)。

游玩世界中壹共有N种区别的怪兽,分别由1到N编号,未来一号怪兽入侵村庄了,JYY想清楚,最少开销稍微体力值才能将拥有村庄中的怪兽整体杀掉呢?

Input

首先行包括二个整数N。

接下去N行,每行描述二个怪兽的消息;

中间第i行李包裹罗若干个整数,前八个整数为Si,Ki和Ri,表示对此i号怪兽,

普通攻击必要消耗Si的体力,法术攻击需求开支Ki的体力,同时i号怪兽寿终正寝后会发生Ri个新的怪兽。表示2个新出现的怪兽编号。同一编号的怪兽能够出现五个。

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的怪兽。

余下3号怪兽开支1点体力举行普通攻击。

此刻村庄里的怪兽编号是二和四。

终极开销11点体力用法术攻击将那八只怪兽彻底杀死。

共计开销的体力是四+5+5+一+5+6=贰陆。

【数据范围】

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

 

 

  这的确是一道很妙的题,反正本身是没做出来的。

  困扰在”三个怪被砍死会长出一批差别的怪”这几个标题上,难道怪物基因都以均等的怎么跑最短路啊。

  去网上看了1波题解发现都讲的很少,就如是因为那题太水?智力障碍选手请过早弃疗。

  要是未有环出现,对它是一个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点体力用普通攻击,然后出现的怪兽编号是二,二和叁。

费用10点体力用法术攻击杀死三个号码为贰的怪兽。

剩余三号怪兽开销一点体力实行普通攻击。

那儿村子里的怪兽编号是二和4。

提起底成本1一点体力用法术攻击将那七只怪兽彻底杀死。

总结消费的体力是肆+五+伍+1+五+6=二陆。

【数据范围】

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

 

 

  那诚然是壹道很妙的题,反正小编是没做出来的。

  困扰在”1个怪被砍死会长出一批区别的怪”这几个标题上,难道怪物基因都是均等的怎么跑最短路啊。

  去网上看了一波题解发现都讲的很少,就如是因为那题太水?智力障碍选手请太早弃疗。

  假如没有环出现,对它是二个DAG,正是二个很水的DP题了,反向拓扑一下。

  然后将来有环了。有环就会有何啊?有后效性。DP是无法化解有后效性的题指标。

  可是SPFA能够。SPFA正是一点1滴未有管后效性的算法(所以很不难被卡?)。

  设把怪净化掉的细微开销是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;
}

  

相关文章