BZOJ 3875 [Ahoi2014]骑士游戏 【SPFA】

tonyfang posted @ 2016年3月06日 08:41 in BZOJ with tags C++ OI , 273 阅读

【题解】建两部分边,跑spfa即可。

 

# include <stdio.h>
# include <queue>
# include <string.h>
using namespace std;

const int N=2100030;
int n;
long long s[N],d[N];
int head[N],next[N],to[N],tot,head2[N],next2[N],to2[N],tot2;
bool vis[N];

inline void add1(int u,int v) {
	tot++;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void add2(int u,int v) {
	tot2++;
	next2[tot2]=head2[u];
	head2[u]=tot;
	to2[tot2]=v;
}

inline void spfa() {
	queue<int> q;
	while(!q.empty()) q.pop();
	for (int i=1;i<=n;++i) q.push(i),vis[i]=1;
	while(!q.empty()) {
		int top=q.front(); q.pop();
		vis[top]=0;
		long long w=s[top];
		for (int i=head[top];i;i=next[i]) 
			w=w+d[to[i]];
		if(w>=d[top]) continue;
		d[top]=w;
		for (int i=head2[top];i;i=next2[i]) {
			if(!vis[to2[i]]) {
				q.push(to2[i]);
				vis[to2[i]]=1;
			}
		}
	}
}

int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) {
		int fu,too;
		scanf("%lld%lld%d",&s[i],&d[i],&fu);
		for (int j=1;j<=fu;++j) {
			scanf("%d",&too);
			add1(i,too);
			add2(too,i);
		}
	}
	spfa();
	printf("%lld\n",d[1]);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter