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

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

【题解】建两部分边,跑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;
}
10thmodelpaper.in 说:
2023年4月21日 20:48

10th Board Model Paper 2023 Aspirants who had Registered for the Board 10th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. 10thmodelpaper.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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