题目大意

数据范围

$0\leqslant n,m\leqslant 500000$,每个ATM机中可取的钱数为一个非负整数且$\leqslant$4000

题解

题目描述已经很明确的说明了每条道路可以经过多次，因此先tarjan缩点把图重建成DAG图

然后再用SPFA跑一边最长路，然后统计每个酒吧为终点的最长路的最大值就行了

程序

#include<cstdio>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define maxn 505000
using namespace std;

struct edge{int to,next;}e[maxn],e2[maxn];
int last[maxn],last2[maxn],c[maxn],c2[maxn];
int dfn[maxn],low[maxn],q[maxn],flag[maxn];
int belong[maxn],d[maxn];
int n,m,s,p,dt,et,et2,top,scc;
inline void addedge(int u,int v){e[++et].to=v;e[et].next=last[u];last[u]=et;}
inline void addedge2(int u,int v){e2[++et2].to=v;e2[et2].next=last2[u];last2[u]=et2;}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void tarjan(int x){
    dfn[x]=low[x]=++dt;
    q[++top]=x;flag[x]=1;
    for(int i=last[x];i;i=e[i].next)
        if (!dfn[e[i].to]) {tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
        else if (flag[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    if (low[x]==dfn[x]){
        ++scc;int now=0;
        while (now!=x){
            now=q[top--];
            belong[now]=scc;
            c2[scc]+=c[now];
            flag[now]=0;
        }
    }
}
inline void rebuild(){
    For(u,1,n)
        for(int i=last[u];i;i=e[i].next)
            if (belong[u]!=belong[e[i].to]) addedge2(belong[u],belong[e[i].to]);
}
inline void spfa(){
    queue <int> q2;memset(flag,0,sizeof(flag));
    d[belong[s]]=c2[belong[s]];q2.push(belong[s]);flag[belong[s]]=1;
    int z=0;
    while (!q2.empty()){
        z++;
        int h=q2.front();q2.pop();flag[h]=0;
        for(int i=last2[h];i;i=e2[i].next)
            if (d[h]+c2[e2[i].to]>d[e2[i].to]){
                d[e2[i].to]=d[h]+c2[e2[i].to];
                if (!flag[e2[i].to]) {q2.push(e2[i].to);flag[e2[i].to]=1;}
            }
    }
}
int main(){
    n=read();m=read();
    For(i,1,m){
        int x=read(),y=read();
        addedge(x,y);
    }
    For(i,1,n) c[i]=read();
    For(i,1,n) if (!dfn[i]) tarjan(i);
    s=read();p=read();int ans=0;
    rebuild();
    spfa();
    For(i,1,p){
        int x=read();
        if (d[belong[x]]>ans) ans=d[belong[x]];
    }
    printf("%d\n",ans);
    return 0;
}