[AHOI2014/JSOI2014]骑士游戏
题目链接:洛谷P4042
Background
长期的宅男生活中，JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会
扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。
Description
在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统bug，并不保证这一点）。
游戏世界中一共有N种不同的怪兽，分别由1到N编号，现在1号怪兽入侵村庄了，JYY想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？
Input
第一行包含一个整数N。
接下来N行，每行描述一个怪兽的信息；
其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽，普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
Output
输出一行一个整数，表示最少需要的体力值。
Sample Input 1
4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2
Sample Output 1
26
Hint
首先用消耗4点体力用普通攻击，然后出现的怪兽编号是2，2和3。花费10点体力用法术攻击杀死两个编号为2的怪兽。剩下3号怪兽花费1点体力进行普通攻击。此时村庄里的怪兽编号是2和4。最后花费11点体力用法术攻击将这两只怪兽彻底杀死。一共花费的体力是4+5+5+1+5+6=26。
所有数据满足
Solution
这一题乍一看是DP……但是仔细一想发现DP做不来
于是就想到了建图……233333
很容易想得到彻底杀死一个怪兽需要消耗的体力是(使用链式前向星建图)
建两组边,分开建,一个连儿子一个连父亲
在刚开始可以暴力点将所有点加入队列23333
如果当前点(x)更新,则将父亲加入队列以便更新
就这样跑一遍SPFA,就能A了！
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
// #define Judge
// #define Online
#define maxn 200100
#define maxm 2001000
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
#define S 1000000
int wpos,len,pos;char wbuf[S],buf[S];
FastIO(){wpos=0,len=0,pos=0;}
inline char gc(){
if (pos==len) pos=0,len=fread(buf,1,S,in);
if (pos==len) return 0; return buf[pos++];
}
inline void wchar(int x) {
if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
wbuf[wpos++]=x;
}
inline void put(const char*s) {for(; *s; ) wchar(*s++);}
~FastIO() {
if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
}
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
queue<ll>que;
ll n,s[maxn],k[maxn],bo[maxn],fir[2][maxn],to[2][maxm],nxt[2][maxm],cnt[2];
inline void ins(ll x,ll y){
nxt[0][++cnt[0]]=fir[0][x],fir[0][x]=cnt[0],to[0][cnt[0]]=y;
nxt[1][++cnt[1]]=fir[1][y],fir[1][y]=cnt[1],to[1][cnt[1]]=x;
}
inline void SPFA(){
for (ll i=1; i<=n; ++i) que.push(i),bo[i]=1;
while(!que.empty()){
ll now=que.front();que.pop(),bo[now]=0;ll tmp=s[now];
for (ll i=fir[0][now]; i; i=nxt[0][i]) tmp+=k[to[0][i]];
if (tmp>=k[now]) continue; k[now]=tmp;
for (ll i=fir[1][now]; i; i=nxt[1][i])
if (bo[to[1][i]]==0) bo[to[1][i]]=1,que.push(to[1][i]);
}
}
int main(int argv,char*argc[]){
read(n);
for (ll r,tmp,i=1; i<=n; ++i){
read(s[i]),read(k[i]),read(r);
while(r--) read(tmp),ins(i,tmp);
}
SPFA();wt(k[1],'\n');
return 0;
}
