[HOJ]235 ATM

一個點可以重覆經過
SCC縮環+SPFA

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAX 500005
using namespace std;
int val[MAX],dis[MAX],p[MAX],nval[MAX];
int fr,to,s,t,tmp,cnt,n,m,ans;
vector<int> ed,nv[MAX];
vector<pair<int,bool> > v[MAX];
queue<int> q;
bool bar[MAX],vis[MAX];
void dfs(int k){
    vis[k]=true;
    for(int i=0;i<v[k].size();i++){
        if(v[k][i].second&&!vis[v[k][i].first])
            dfs(v[k][i].first);
    }
    ed.push_back(k);
}
void dfs2(int k,int num){
    p[k]=num;
    nval[num]-=val[k];
    vis[k]=true;
    for(int i=0;i<v[k].size();i++){
        if(!v[k][i].second&&!vis[v[k][i].first])
            dfs2(v[k][i].first,num);
    }
}
void dfs3(int k){
    for(int i=0;i<v[k].size();i++)
        if(v[k][i].second&&p[v[k][i].first]!=p[k])
            nv[p[k]].push_back(p[v[k][i].first]);   
} 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fr,&to);
        v[fr].push_back(make_pair(to,1));
        v[to].push_back(make_pair(fr,0));
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        dis[i-1]=1000000000;
    }
    scanf("%d%d",&s,&t);
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i);
    memset(vis,0,sizeof(vis));
    for(int i=n-1;i>=0;i--)
        if(!vis[ed[i]])dfs2(ed[i],cnt++);
    for(int i=1;i<=n;i++)
        dfs3(i);
    memset(vis,0,sizeof(vis));
    dis[p[s]]=nval[p[s]];
    vis[p[s]]=true;
    q.push(p[s]);
    while(!q.empty()){
        tmp=q.front();
        q.pop();
        vis[tmp]=0;
        for(int i=0;i<nv[tmp].size();i++){
            if(dis[tmp]+nval[nv[tmp][i]]<dis[nv[tmp][i]]){
                dis[nv[tmp][i]]=dis[tmp]+nval[nv[tmp][i]];
                if(!vis[nv[tmp][i]]){
                    q.push(nv[tmp][i]); 
                    vis[nv[tmp][i]]=true;       
                }
            }   
        }
    }
    for(int i=0;i<t;i++){
        scanf("%d",&tmp);
        ans=min(ans,dis[p[tmp]]);
    }
    printf("%d\n",-ans);
}