玄一关,求条
查看原帖
玄一关,求条
661638
lkjzyd20楼主2024/12/29 12:28
#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
#define A(x,y) V[x].push_back(y)
using namespace std;
const int N=2e5+10;
vector<int> V[N],V1[N];
int dfn[N],low[N],ti,cnt,f[N],st[N],top,n,m,x,y,val[N],k,t,a[N],P[N],s,p,dist[N],ans;
bool vis[N];
void dfs(int x){
    low[x]=dfn[x]=++ti;st[++top]=f[x]=x;vis[x]=1;
    for(int v:V[x]){
        if(!dfn[v])dfs(v),low[x]=min(low[x],low[v]);
        else if(vis[v])low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x]){
        ++cnt;
        do{f[st[top]]=cnt;val[cnt]+=a[st[top]];vis[st[top]]=0;--top;}while(st[top+1]!=x);
    }
}
struct E{
    int pos,val;
    bool operator<(E x)const{return x.val<val;}
};
void SPFA()
{
    memset(dist,-0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    queue<E>q;
    dist[f[s]]=val[f[s]];
    q.push({f[s], dist[f[s]]});
    for(;!q.empty();)
    {
        E xx=q.front();q.pop();
        int x=q.front().pos;
        for(int v:V1[x])
            if(dist[v]<dist[x]+val[v])
                dist[v]=dist[x]+val[v],q.push({v,dist[v]});
    }
}
main(){
    cin>>n>>m;
    rep(i,1,m)cin>>x>>y,A(x,y);
    rep(i,1,n)cin>>a[i];
    cin>>s>>p;
    rep(i,1,p)cin>>P[i];
    dfs(s);
    rep(i,1,n)
        for(int v:V[i]){
            if(f[i]==f[v])continue;
            V1[f[i]].push_back(f[v]);
        }
    SPFA();
    rep(i,1,p)ans=max(ans,dist[f[P[i]]]);
    printf("%d",ans);
    return 0;
}
2024/12/29 12:28
加载中...