第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 int n,m,cnt,s,p,tim,top,scc,newcnt,ans;
 8 struct data{
 9     int next,to;
10 }edge[500010],newmap[500010];
11 bool check[500010];
12 int head[500010],mon[500010],dfn[500010],low[500010],stack[500010],belong[500010],val[500010],newhd[500010],w[500010];
13 queue<int>q;
14 void add(int start,int end){
15     edge[++cnt].next=head[start];
16     edge[cnt].to=end;
17     head[start]=cnt;
18 }
19 void addnew(int start,int end){
20     newmap[++newcnt].next=newhd[start];
21     newmap[newcnt].to=end;
22     newhd[start]=newcnt;
23 }
24 void tarjan(int x){
25     dfn[x]=low[x]=++tim;
26     stack[++top]=x;
27     check[x]=1;
28     for(int i=head[x];i;i=edge[i].next)
29         if(!dfn[edge[i].to]){
30             tarjan(edge[i].to);
31             low[x]=min(low[x],low[edge[i].to]);
32         }
33         else if(check[edge[i].to]) low[x]=min(low[x],dfn[edge[i].to]);//!!!
34     int tmp;
35     if(low[x]==dfn[x]){
36         scc++;
37         do{
38             tmp=stack[top--];
39             belong[tmp]=scc;
40             val[scc]+=mon[tmp];
41             check[tmp]=0;
42         }while(tmp!=x);
43     }    
44 }
45 void solve(){
46     for(int i=1;i<=n;i++)
47         if(!dfn[i]) tarjan(i);
48     for(int i=1;i<=n;i++)
49         for(int j=head[i];j;j=edge[j].next)
50             if(belong[i]!=belong[edge[j].to]) addnew(belong[i],belong[edge[j].to]);
51 }
52 void spfa(){
53     memset(check,0,sizeof(check));
54     check[belong[s]]=1;
55     w[belong[s]]=val[belong[s]];
56     q.push(belong[s]);
57     while(!q.empty()){
58         int p=q.front();
59         q.pop();
60         check[p]=0;
61         for(int i=newhd[p];i;i=newmap[i].next)
62             if(w[newmap[i].to]<w[p]+val[newmap[i].to]){
63                 w[newmap[i].to]=w[p]+val[newmap[i].to];
64                 if(!check[newmap[i].to]){
65                     check[newmap[i].to]=1;
66                     q.push(newmap[i].to);
67                 }
68             }
69     }
70 }
71 int main(){
72     scanf("%d%d",&n,&m);
73     int u,v;
74     for(int i=1;i<=m;i++){
75         scanf("%d%d",&u,&v);
76         add(u,v);
77     }
78     for(int i=1;i<=n;i++) scanf("%d",&mon[i]);
79     scanf("%d%d",&s,&p);
80     solve();
81     spfa();
82     int a;
83     for(int i=1;i<=p;i++){
84         scanf("%d",&a);
85         ans=max(ans,w[belong[a]]);
86     }
87     printf("%d",ans);
88     return 0;
89 }