1 #include<cstdio>  2 #include<cstring>  3 using namespace std;  4 const int N=500010,novis=-1,over=1,nowvis=0;  5 int head1[N],head2[N],value[N],n,m,size,ans;  6 int low[N],dfn[N],flag[N],que[N],sum[N],color[N],  7     cnt,sig,top;  8 int zh[N],vis[N],dis[N];  9 struct fx{ 10     int to,next; 11 }e1[N],e2[N]; 12 int min(int,int),max(int,int),read(); 13 void dfs(int),tarjan(),rebuild(),spfa(int); 14 void uni2(int,int),uni(int,int); 15 int main(){ 16     int x,y,p,tmp,s; 17     memset(head1,0,sizeof(head1)); 18     size=ans=0; 19     n=read();m=read(); 20     for (int i=1;i<=m;i++){ 21         x=read();y=read(); 22         uni(x,y); 23     } 24     for (int i=1;i<=n;i++) 25         value[i]=read(); 26     s=read();p=read(); 27     tarjan(); 28     spfa(color[s]); 29     for (int i=1;i<=p;i++){ 30         tmp=read(); 31         ans=max(ans,dis[color[tmp]]); 32     } 33     printf("%d",ans); 34     return 0; 35 } 36 void uni(int x,int y){ 37     size++; 38     e1[size].next=head1[x]; 39     head1[x]=size; 40     e1[size].to=y; 41 } 42 void uni2(int x,int y){ 43     size++; 44     e2[size].next=head2[x]; 45     head2[x]=size; 46     e2[size].to=y; 47 } 48 void tarjan(){ 49     sig=cnt=top=0; 50     memset(flag,novis,sizeof(flag)); 51     memset(color,0,sizeof(color)); 52     memset(sum,0,sizeof(sum)); 53     for (int i=1;i<=n;i++) 54         if (flag[i]==novis) dfs(i); 55     rebuild(); 56 } 57 void dfs(int x){ 58     flag[x]=nowvis; 59     low[x]=dfn[x]=++sig; 60     que[++top]=x; 61     for (int e=head1[x];e;e=e1[e].next){ 62         int v=e1[e].to; 63         if (flag[v]==novis){ 64             dfs(v); 65             low[x]=min(low[x],low[v]); 66         } 67         else if (flag[v]==nowvis) 68             low[x]=min(low[x],dfn[v]); 69     } 70     if (low[x]==dfn[x]){ 71         cnt++;int t; 72         do{ 73             t=que[top--]; 74             flag[t]=over; 75             color[t]=cnt; 76             sum[cnt]+=value[t]; 77         }while (t!=x); 78     } 79 } 80 void rebuild(){ 81     int v;size=0; 82     for (int u=1;u<=n;u++) 83         for (int e=head1[u];e;e=e1[e].next){ 84             v=e1[e].to; 85             if (color[u]!=color[v])  86                 uni2(color[u],color[v]); 87         } 88 } 89 void spfa(int st){ 90     int r,l,u,v; 91     memset(vis,0,sizeof(vis)); 92     memset(dis,0,sizeof(dis)); 93     r=1;l=0; zh[l]=st; vis[st]=1; 94     dis[st]=sum[st]; 95     while (l<=r){ 96         u=zh[l++]; 97         if (l==N) l=0; 98         for (int e=head2[u];e;e=e2[e].next){ 99             v=e2[e].to;100             if (dis[v]<dis[u]+sum[v]){101                 dis[v]=dis[u]+sum[v];102                 if (!vis[v]){103                     vis[v]=1;zh[r++]=v;104                     if (r==N) r=0;105                 }   106             }107          }108          vis[u]=0;109     }110 }111 int min(int x,int y){112     return x<y?x:y;113 }114 int max(int x,int y){115     return x>y?x:y;116 }117 int read(){118     int ss=0;char c;119     c=getchar();120     while (c<‘0‘||c>‘9‘) c=getchar();121     while (c>=‘0‘&&c<=‘9‘){122         ss=ss*10+c-‘0‘;c=getchar();123     }124     return ss;125 }