传送门

分析

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们发现对于一个怪物要不然用魔法代价使其无需考虑后续点要么用普通攻击使其转移到他所连的所有点上且所有边大于0

所以我们可以先将一个点的最优代价设为魔法攻击的代价

之后我们倒着跑spfa求出最短路即可

代码

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<ctime> #include<queue> #include<vector> #include<set> #include<map> #include<stack>
using namespace std; #define int long long
int d[200100],a[200100],n,iq[200100]; vector<int>v1[200100],v2[200100]; queue<int>q; inline void spfa(){ int i,j,k; for(i=1;i<=n;i++)q.push(i),iq[i]=1; while(!q.empty()){ int x=q.front(); q.pop(); iq[x]=0; int res=a[x]; for(i=0;i<v1[x].size();i++)res+=d[v1[x][i]]; if(res<d[x]){ d[x]=res; for(i=0;i<v2[x].size();i++) if(!iq[v2[x][i]])q.push(v2[x][i]),iq[v2[x][i]]=1; } } } signed main(){ int i,j,k,x; scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld%lld%lld",&a[i],&d[i],&k); while(k--){ scanf("%lld",&x); v1[i].push_back(x); v2[x].push_back(i); } } spfa(); cout<<d[1]<<endl; return 0; }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄