题目描述
有$n$个怪兽，每个怪兽可以花费$k_i$的代价消灭，或者花费$s_i$的代价将其变为$r_i$个给定的新的怪兽。问消灭1号怪兽的最小代价。
输入
第一行包含一个整数N。
接下来N行，每行描述一个怪兽的信息；
其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽，
普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
输出
输出一行一个整数，表示最少需要的体力值。
样例输入
4 4 27 3 2 3 2 3 5 1 2 1 13 2 4 2 5 6 1 2
样例输出
26
题解
Spfa优化dp
设$f[i]$表示消灭$i$号怪兽的最小代价，那么显然有状态转移方程$f[i]=min\{k[i],s[i]+\sum\limits_{i\to x}f[x]\}$。
但是这个转移是有环的，因此爆搜是指数级= =
考虑优化dp：设$g[i]$表示$i$用于更新其它点的代价，那么当一个点的$g[i]>f[i]$时，便可以使能变成它的其它点的$f$值减小$g[i]-f[i]$。这个过程类似于最短路，因此可以使用Spfa来优化这个过程。
初始时$f[i]=k[i]$，$g[i]=s[i]+\sum\limits_{i\to x}k[x]$，然后转移即可。
时间复杂度$O(Spfa)=O(能过)$
另外本题可以使用类似于堆优化Dijkstra的优化dp方法解决，参见
#include#include #include #include #define N 200010#define M 1000010using namespace std;typedef long long ll;queue q;int head[N] , to[M] , next[M] , cnt , inq[N];ll v[N] , f[N] , g[N];inline char nc(){ static char buf[100000] , *p1 , *p2; return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}inline int read(){ int ret = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc(); return ret;}inline ll llread(){ ll ret = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc(); return ret;}inline void add(int x , int y){ to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}int main(){ int n = read() , i , m , x; for(i = 1 ; i <= n ; i ++ ) { v[i] = llread() , g[i] = llread() , m = read() , inq[i] = 1 , q.push(i); while(m -- ) add(read() , i); } for(x = 1 ; x <= n ; x ++ ) { f[x] += v[x]; for(i = head[x] ; i ; i = next[i]) f[to[i]] += g[x]; } while(!q.empty()) { x = q.front() , q.pop() , inq[x] = 0; if(f[x] >= g[x]) continue; for(i = head[x] ; i ; i = next[i]) { f[to[i]] -= g[x] - f[x]; if(!inq[to[i]]) inq[to[i]] = 1 , q.push(to[i]); } g[x] = f[x]; } printf("%lld\n" , f[1]); return 0;}