记录编号	432370	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.075 s
提交时间	2017-08-03 11:02:20	内存使用	30.83 MiB

#include<bits/stdc++.h>/*缩完点之后将每个点的权值赋值给指向他的边，spfa求最长路即可*/
using namespace std;
const int inf=500005;
int s,p[inf],P,n,m,head[inf],C[inf],h,low[inf],pre[inf],scc[inf],scc_cnt,scc_time,hea[inf],h2,c[inf],dis[inf],vis[inf];
struct edge{
	int to,next,cost;
}e[inf],e2[inf];
queue<int>Q;
void edge_add(int x,int y,int z){
	e[++h].to=y;
	e[h].cost=z;
	e[h].next=head[x];
	head[x]=h;
}
void edge_Add(int x,int y,int z){
	e2[++h2].to=y;
	e2[h2].cost=z;
	e2[h2].next=hea[x];
	hea[x]=h2;
}
stack<int>S;
void dfs(int x){
	low[x]=pre[x]=++scc_time;
	S.push(x);
	for(int i=head[x];i;i=e[i].next){
		int u=e[i].to;
		if(!pre[u]){
			dfs(u);
			low[x]=min(low[x],low[u]);
		}
		else if(!scc[u]){
			low[x]=min(low[x],low[u]);
		}
	}
	if(pre[x]==low[x]){
		scc_cnt++;
		for(;;){
			int v=S.top();
			S.pop();
			scc[v]=scc_cnt;
			if(x==v)
			break;
		}
	}
}
void tarjan_suo(){
	for(int i=1;i<=n;i++)
	if(!pre[i])dfs(i);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=e[j].next){
			if(scc[i]!=scc[e[j].to]){
				edge_Add(scc[i],scc[e[j].to],0);
			}
		}
	}
	for(int i=1;i<=n;i++)
	C[scc[i]]+=c[i];
//	for(int i=1;i<=scc_cnt;i++)cout<<C[i]<<" ";
	for(int i=1;i<=scc_cnt;i++){
		for(int j=hea[i];j;j=e2[j].next){
			e2[j].cost=C[e2[j].to];
		}
	}
}
void spfa(){
	vis[scc[s]]=1;
	Q.push(scc[s]);
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		vis[u]=0;
		for(int i=hea[u];i;i=e2[i].next){
			if(dis[e2[i].to]<dis[u]+e2[i].cost){
				dis[e2[i].to]=dis[u]+e2[i].cost;
				if(!vis[e2[i].to]){
					Q.push(e2[i].to);
					vis[e2[i].to]=1;
				}
			}
		}
	}
	int ma=-1;
	for(int i=1;i<=P;i++){
		ma=max(ma,dis[scc[p[i]]]);
	}
	ma+=C[scc[s]];
	cout<<ma;
}
int main()
{
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		edge_add(x,y,0);
	}
	for(int i=1;i<=n;i++)
	scanf("%d",&c[i]);
	scanf("%d%d",&s,&P);
	for(int i=1;i<=P;i++)
	scanf("%d",&p[i]);
	tarjan_suo();
	spfa();
	return 0;
}