比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 TARDIS 运行时间 0.041 s
代码语言 C++ 内存使用 24.64 MiB
提交时间 2017-05-22 17:46:01
显示代码纯文本
#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=500100;
vector<int> G[maxn];
vector<int> T[maxn];
int money[maxn],n,m,summ[maxn];
int from,to,temp,s,p;
int dfn[maxn],low[maxn],dfs_clock,belong[maxn],scc_cnt,dis[maxn];
bool instack[maxn],inque[maxn],f[maxn];
stack<int> st;
inline void PRINT(int *a,int n){
	for (int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	puts("");
}
inline void in(){
	#ifdef COGS
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&from,&to);
		G[from].push_back(to);
	}
	for (int i=1;i<=n;i++){
		scanf("%d",&money[i]);
	}
	scanf("%d%d",&s,&p);
}
inline void dfs(int now){
	if (dfn[now]) return;
	dfs_clock++;
	low[now]=dfn[now]=dfs_clock;
	st.push(now),instack[now]=1;
	int num=G[now].size();
	for (int i=0;i<num;i++){
		int go=G[now][i];
		if (!dfn[go]){
			dfs(go);
			low[now]=min(low[now],low[go]);
		}
		else if (instack[go]){
			low[now]=min(low[now],dfn[go]);
		}
	}
	if (low[now]==dfn[now]){
		scc_cnt++;int j;
		do{
			j=st.top();
			st.pop();instack[j]=0;
			belong[j]=scc_cnt;
			summ[scc_cnt]+=money[j];
		}while(j!=now);
	}
}
inline void tarjan_bg(){
	for (int i=1;i<=n;i++){
		dfs(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<G[i].size();j++)
		{
			if(belong[i]!=belong[G[i][j]])
			T[belong[i]].push_back(belong[G[i][j]]);
	}
}
}
inline void SPFA(int s){
	queue<int> que;
	memset(dis,-64,sizeof(dis));
	dis[s]=summ[s];
	que.push(s),inque[s]=1;
	while(!que.empty()){
		int u=que.front();que.pop();inque[u]=0;
		int num=T[u].size();
		for (int i=0;i<num;i++){
			int to=T[u][i];
			if (dis[to]<dis[u]+summ[to]){
				dis[to]=dis[u]+summ[to];
				if (!inque[to]){
					que.push(to);
					inque[to]=1;
				}
			}
		}
	}
}
inline void deal(){
	tarjan_bg();
	SPFA(belong[s]);
}

inline void pr(){
	int ans=-1,t;
	for (int i=1;i<=p;i++){
		scanf("%d",&t);
		ans=max(ans,dis[belong[t]]);
	}
	//PRINT(belong,n);
	printf("%d",ans);
}
int Main(){
	freopen("a.txt","r",stdin);
	in();
	deal();
	pr();
	return 0;
}
int main(){;}
int xlm=Main();