前往>>暴风城
第一次写SPFA！（惭愧
对于某个怪兽，杀死它的最小消耗 = min（它的魔法消耗，它的物理消耗 + 杀死它所有儿子的消耗）
可以看出，一个点可能被它的儿子更新，并且可能去更新它的父亲。
考虑用最短路解决这道题，从一个假设的起点0出发，要求它到1的最短距离。1~n每个点的距离初始应为INF。
将每个怪物的消耗更新为它的魔法消耗，并加入队列；
弹出队首，检查它能不能被更新。如果可以，则说明它有可能更新它的父亲，将它的所有父亲加入队列；
直到队列为空为止。
代码如下
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #define MogeKo qwq #include<queue> using namespace std; const int maxn = 2e6; int n,r,x; long long ad[maxn],ap[maxn],dis[maxn]; int head[maxn][2],to[maxn][2],nxt[maxn][2],cnt[2]; bool vis[maxn]; queue <int> q; void add(int x,int y,int op) { to[++cnt[op]][op] = y; nxt[cnt[op]][op] = head[x][op]; head[x][op] = cnt[op]; } void SPFA() { for(int i = 1; i <= n; i++) { q.push(i); vis[i] = true; } while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; long long tem = ad[u]; for(int i = head[u][1]; i; i = nxt[i][1]) tem += dis[to[i][1]]; if(tem >= dis[u])continue; dis[u] = tem; for(int i = head[u][0]; i; i = nxt[i][0]) { int v = to[i][0]; if(vis[v])continue; q.push(v); vis[v] = true; } } } int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%lld%lld%d",&ad[i],&ap[i],&r); dis[i] = ap[i]; for(int j = 1; j <= r; j++) { scanf("%d",&x); add(x,i,0); add(i,x,1); } } SPFA(); printf("%lld",dis[1]); return 0; }
原文：https://www.cnblogs.com/mogeko/p/10877749.html
