bzoj 1179 [Apio2009]Atm——SCC缩点+spfa

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1179

显然SCC缩点。

然后准备倒着拓扑序推到st，结果WA。

听TJ说dj求最长路会发生不好的事情，于是学TJ用了spfa。

因为是有向边所以别再tarjan里判fa！！！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=5e5+;

int n,m,cnt,hd[N],thd[N],st,ps,rd[N];

int dfn[N],low[N],tim,sta[N],top,col[N];

bool b[N],p[N],r[N],ins[N];

ll c[N],q[N],dis[N],ans;

struct Ed{

  int nxt,tnxt,fr,to;

  Ed(int n=,int f=,int t=):nxt(n),fr(f),to(t) {tnxt=;}

}ed[N];

void tarjan(int cr)

{

  dfn[cr]=low[cr]=++tim;

  sta[++top]=cr;ins[cr]=;

  for(int i=hd[cr],v;i;i=ed[i].nxt)

      if(!dfn[v=ed[i].to])

    {

      tarjan(v);low[cr]=min(low[cr],low[v]);

    }

      else if(ins[v])low[cr]=min(low[cr],dfn[v]);

  if(dfn[cr]==low[cr])

    {

      cnt++;

      while(sta[top]!=cr)

    {

      r[cnt]|=p[sta[top]];c[cnt]+=q[sta[top]];

      col[sta[top]]=cnt;ins[sta[top--]]=;

    }

      top--;col[cr]=cnt;ins[cr]=;

      r[cnt]|=p[cr];c[cnt]+=q[cr];

    }

}

void spfa()

{

    dis[col[st]]=c[col[st]];

    memset(ins,,sizeof ins);ins[col[st]]=;

    queue<int> q;q.push(col[st]);

    while(q.size())

    {

        int k=q.front();q.pop();ins[k]=;

        for(int i=thd[k],v;i;i=ed[i].tnxt)

            if(dis[k]+c[v=col[ed[i].to]]>dis[v])

            {

                dis[v]=dis[k]+c[v];

                if(!ins[v])ins[v]=,q.push(v);

            }

    }

}

int main()

{

  scanf("%d%d",&n,&m);int x,y;

  for(int i=;i<=m;i++)

    {

      scanf("%d%d",&x,&y);

      ed[i]=Ed(hd[x],x,y);hd[x]=i;

    }

  for(int i=;i<=n;i++)scanf("%lld",&q[i]);

  scanf("%d%d",&st,&ps);

  for(int i=;i<=ps;i++)

    {

      scanf("%d",&x);p[x]=;

    }

  for(int i=;i<=n;i++)if(!dfn[i])tarjan(i);

  for(int i=,v;i<=m;i++)

    if((v=col[ed[i].fr])!=col[ed[i].to])

      ed[i].tnxt=thd[v],thd[v]=i;

  spfa();

//      ed[i].tnxt=thd[v],thd[v]=i,rd[u]++;

//  int h=0,t=0;

//  for(int i=1;i<=cnt;i++)

//    if(!rd[i])sta[++t]=i;

//  while(h<=t)

//    {

//      int k=sta[++h];lj[k]+=c[k];b[k]|=r[k];

//      if(!b[k])lj[k]=0;

//      for(int i=thd[k],v;i;i=ed[i].tnxt)

//    {

//      rd[v=col[ed[i].fr]]--;

//      lj[v]=max(lj[v],lj[k]);b[v]|=b[k];

//      if(!rd[v])sta[++t]=v;

//    }

//    }

//  printf("%lld\n",lj[col[st]]);

  for(int i=;i<=cnt;i++)if(r[i])ans=max(ans,dis[i]);

  printf("%lld\n",ans);

  return ;

}