bzoj 1179 ATM tarjan缩点+spfa最短路

题目链接

#include<cstring>//裸的 tajian+spfa
#include<ctype.h>
#include<cstdio>
#include<queue>
#define N 1000005
using namespace std;
bool in[N],pp[N],vis[N],v[N];
int bel[N],VAL[N],size[N],hea[N],val[N],sta[N],low[N],dnf[N],hea2[N],dis[N];
int tot,ans,top,pt,dfs_clock,s,p,x,y,n,m;
struct NODE{
     int nex,to;
}nex[N]; 
NODE nex2[N];
inline void add(int x,int y){
	nex[++tot].nex=hea[x];
	nex[tot].to=y;
	hea[x]=tot;
}
int input(){
	char c='^';
	int sum=0;
	c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
return sum;
}
void tajian(int curr){
    vis[sta[++top]=curr]=1;
    dnf[curr]=low[curr]=++dfs_clock;
    for(int i=hea[curr];i;i=nex[i].nex){
        if(!dnf[nex[i].to]){
            tajian(nex[i].to);
            low[curr]=min(low[curr],low[nex[i].to]);
        }
        else if(vis[nex[i].to]){
            low[curr]=min(low[curr],dnf[nex[i].to]);
        }
    }
    if(low[curr]==dnf[curr]){
        vis[curr]=0;
        VAL[bel[curr]=++tot]+=val[curr];
        while(sta[top]!=curr){
            VAL[bel[sta[top]]=tot]+=val[sta[top]];
            vis[sta[top--]]=0;
        }
        top--;
    }
}
inline void rbuild(){//重新建边
	for(int i=1;i<=n;i++)
		for(int j=hea[i];j;j=nex[j].nex){
			int dmf=nex[j].to;
			if(bel[i]!=bel[dmf]){
				nex2[++tot].to=bel[dmf];
				nex2[tot].nex=hea2[bel[i]];
				hea2[bel[i]]=tot;
			} 
		}
}
inline void spfa(int s){
    queue <int>q ;
    dis[s]=VAL[s];
    v[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=hea2[x];i;i=nex2[i].nex){
            if(dis[x]+VAL[nex2[i].to]>dis[nex2[i].to]){
                dis[nex2[i].to]=dis[x]+VAL[nex2[i].to];
                if(!v[nex2[i].to]){
                    v[nex2[i].to]=1;
                    q.push(nex2[i].to);
                }
            }
        }
        v[x]=0;
    }
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		x=input();y=input();
		add(x,y);
	}
	for(int i=1;i<=n;i++)
		val[i]=input();
	s=input();p=input();
	for(int i=1;i<=n;i++)
		if(!bel[i]) tajian(i);
	tot=0;
	rbuild();
	spfa(bel[s]);
	ans=0;
	for(int i=1;i<=p;i++){
		x=input();
		ans=max(ans,dis[bel[x]]);
	}
	printf("%d",ans);
	return 0;
}