题目 https://www.luogu.com.cn/problem/P4042
分析
如果我想普通攻击 1, 那么必须干掉所有产生的其它怪兽, 这不由得可以用一个不等式来表示,
\(普攻 +\sum need < 法攻 \)
但是所需要消灭的怪兽同样可以这样进行, 所以它可能具有后效性, 那不就是 SPFA 吗
代码
- #include <cstdio>
- #include <cctype>
- #include <queue>
- #define rr register
- using namespace std;
- const int N=200011; long long dis[N],tur[N];
- struct node{int y,next;}e[N*5],E[N*5];
- int v[N],n,k=1,ls[N],hs[N]; queue<int>q;
- inline long long iut(){
- rr long long ans=0; rr char c=getchar();
- while (!isdigit(c)) c=getchar();
- while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
- return ans;
- }
- inline void add(int x,int y){
- e[++k]=(node){y,ls[x]},ls[x]=k;
- E[k]=(node){x,hs[y]},hs[y]=k;
- }
- signed main(){
- n=iut();
- for (rr int i=1;i<=n;++i){
- tur[i]=iut(),dis[i]=iut();
- for (rr int cnt=iut();cnt;--cnt) add(i,iut());
- }
- for (rr int i=1;i<=n;++i) v[i]=1,q.push(i);
- while (q.size()){
- rr int x=q.front(); q.pop(); v[x]=0;
- rr long long t=tur[x];
- for (rr int i=ls[x];i;i=e[i].next) t+=dis[e[i].y];
- if (t>=dis[x]) continue; dis[x]=t;
- for (rr int i=hs[x];i;i=E[i].next)
- if (!v[E[i].y]) v[E[i].y]=1,q.push(E[i].y);
- }
- return !printf("%lld",dis[1]);
- }
来源: http://www.bubuko.com/infodetail-3382670.html