P4042 骑士游戏 [spfa 实现 DP]

本文主要是介绍P4042 骑士游戏 [spfa 实现 DP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

f[x] 表示把x杀死的最小花费  

我们发现, 只要有一个to 更新了它的f , 对x是有影响的 , 于是我们将to 向x 连边, 跑一个spfa

只要x 的答案被更新 , 就将x入队继续去更新其余的答案

#include<bits/stdc++.h>
#define N 200050
#define M 1000050
#define inf 1000000000000000
#define LL long long
using namespace std;int first[N],next[M],to[M],tot;
vector<int> a[N];
int n,vis[N];
LL s[N],k[N],dis[N];
void add(int x,int y){next[++tot]=first[x],first[x]=tot,to[tot]=y;
}
LL spfa(){queue<int> q;for(int i=1;i<=n;i++){dis[i] = k[i]; vis[i] = 1, q.push(i);}while(!q.empty()){int x = q.front(); q.pop(); vis[x] = 0;LL tmp = s[x]; int Siz = a[x].size();for(int i=0;i<Siz;i++) tmp += dis[a[x][i]];if(dis[x]>tmp){dis[x] = tmp;for(int i=first[x];i;i=next[i]){int t=to[i]; if(!vis[t]) vis[t] = 1, q.push(t);}} } return dis[1];
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&s[i],&k[i]);int t; scanf("%d",&t);for(int j=1;j<=t;j++){int x; scanf("%d",&x);add(x,i);  a[i].push_back(x);}} printf("%lld",spfa()); return 0;
}

 

这篇关于P4042 骑士游戏 [spfa 实现 DP]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---