https://www.lydsy.com/JudgeOnline/problem.php?id=1179
题意：一个城市中有许多由单向路连接的路口，每个路口的ATM机里有不同的钱数，有的路口上有酒吧，从给定的出发路口出发，可以经过同一路口或道路任意多次，但只要他抢劫过某个ATM机后，该ATM机里面就不会再有钱了，最终要达到某一酒吧，求最终能取得的总钱数最大是多少。
很考验缩点基本功的题，我写的时候WA了11发，因为各种各样奇怪的小细节各种姿势花式WA，还是太不扎实了。。。
显然对于一个强连通块的路口，只要到达其中任意一个就可以到达这一个块里所有路口，所以先Tarjan缩点，缩点后的每个节点的钱数是这个块里所有点的钱数和，这个块里有酒吧就标注为有酒吧的节点。
然后我们就得到了一个DAG，剩下的就是求最长路了，当然这里的最长表示的是路上节点权值和最大，貌似也不好DP吧，跑一个SPFA就可以了。
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>using namespace std;
const int maxn=500010,maxm=500010;
int dfn[maxn],low[maxn],head1[maxn],head2[maxn],color[maxn],sum[maxn],a[maxn];
int n,m,k,cnt,deep,s,ss,P;
long long ans,dis[maxn],dp[maxn];
bool vis[maxn],p[maxn],pp[maxn];
struct edge{int v,next;
}e1[maxm],e2[maxm];stack<int> st;void addedge1(int u,int v){e1[k].v=v;e1[k].next=head1[u];head1[u]=k++;}
void addedge2(int u,int v){e2[k].v=v;e2[k].next=head2[u];head2[u]=k++;}void tarjan(int u)
{deep++;dfn[u]=deep;low[u]=deep;vis[u]=1;st.push(u);for(int i=head1[u];~i;i=e1[i].next){int v=e1[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else{if(vis[v]){low[u]=min(low[u],low[v]);}}}if(dfn[u]==low[u]){cnt++;color[u]=cnt;vis[u]=0;while(st.top()!=u){color[st.top()]=cnt;vis[st.top()]=0;st.pop();}st.pop();}
}
void spfa(int S)
{memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));queue<int> q;dis[S]=sum[S];vis[S]=1;q.push(S);while(!q.empty()){int t=q.front();vis[t]=0;q.pop();for(int i=head2[t];~i;i=e2[i].next){int v=e2[i].v;//printf("%d\n",v);if(dis[v]<dis[t]+sum[v]){dis[v]=dis[t]+sum[v];if(!vis[v]){vis[v]=1;q.push(v);}}}}
}
int main()
{int x,y;memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);addedge1(x,y);}for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d%d",&s,&P);for(int i=1;i<=P;i++){scanf("%d",&x);p[x]=1;}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=n;i++)sum[color[i]]+=a[i];k=0;for(int i=1;i<=n;i++){for(int j=head1[i];~j;j=e1[j].next){if(color[i]!=color[e1[j].v])addedge2(color[i],color[e1[j].v]);}}spfa(color[s]);for(int i=1;i<=n;i++){if(p[i])ans=max(ans,dis[color[i]]);}printf("%lld\n",ans);return 0;
}