题目反向翻译：
The roads in Siruseri are one-way. Different roads are connected by intersections. According to the law, one is set up at each intersection
A bank ATM of i bank. Surprisingly, Siruseri‘s bars are also located at intersections, although not every intersection has a bar.
Ji plans to implement Siruseri‘s most spectacular ATM robbery ever. He headed into the city center, shifted through the one-way road, and robbed him all.
Approaching the ATM, he will eventually celebrate his victory in a bar. Using superb hacking techniques, he learned what can be plundered in each ATM machine
He wants you to help him calculate the maximum amount of cash he can rob from the city center and finally reach a bar. He can go through the same intersection
Or the road any number of times. But as long as he has robbed a certain ATM machine, there will be no more money in the ATM machine. For example, suppose there are 6 in the city
The junction and road connections are shown in the following figure:
The city center is at intersection 1, marked by an entrance sign →, and those intersections with bars are represented by double circles. The amount of money available in each ATM is marked
In this example, the total cash that Banditji can rob is 47, and the robber route implemented is: 1-2-4-1-2-3-5.
input value
The first line contains two integers N, M. N represents the number of intersections, and M represents the number of roads.
The next M lines, two integers per line, these two integers are between 1 and N,
The two integers on line i + 1 represent the intersection numbers of the start and end points of the i-th road.
The next N lines, each line is an integer, which sequentially represents the amount of money in the ATM machine at each intersection.
The next line contains two integers, S, P, S represents the number of the city center, which is the starting intersection. P is the number of bars.
There are P integers in the next line, indicating the number of P intersections with bars
N, M <= 500000. The amount of money available in each ATM is a non-negative integer and does not exceed 4000.
Entering data guarantees that you can reach the at least one of the bars from the one-way road that transitions from the city centre to Siruseri.
Output
Output an integer indicating the total amount of cash Banditji can rob from the city center to the end of a bar.
做法很显然
先缩点，新图中每个点的点权是原图中他所代表的强连通分量内所有点的点权和
然后把新图建反图（边都反一下），然后从每个酒吧开始跑树形dp，dp出最大点权和
dijkstra好像会TLE，反正我当时的代码里写了但是被注释掉了。。现在也想不起来为什么注释掉
时间复杂度 \(O(n)\)
// This code writed by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=500050;
struct Edge
{
int nxt,to;
}E[MaxN<<2],nE[MaxN<<2];
template <class t> inline void read(t &s)
{
s=0;
reg int f=1;
reg char c=getchar();
while(!isdigit(c))
{
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c))
s=(s<<3)+(s<<1)+(c^48),c=getchar();
s*=f;
return;
}
int hd[MaxN],nhd[MaxN],en,nen,n,m;
int cost[MaxN];
int dfn[MaxN],low[MaxN],dep;
int col[MaxN],scccost[MaxN],scc;
int sta[MaxN],top;
bool instack[MaxN];
vector<int> bar;
inline void adde(int u,int v)
{
++en;
E[en]=(Edge){hd[u],v};
hd[u]=en;
return;
}
inline void nadde(int u,int v)
{
++nen;
nE[nen]=(Edge){nhd[u],v};
nhd[u]=nen;
return;
}
/*inline void tarjan(int u)
{
dfn[u]=low[u]=++dep;
sta[top++]=u;
instack[u]=true;
for(int i=hd[u];~i;i=E[i].nxt)
{
reg int v=E[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++scc;
do
{
--top;
instack[sta[top]]=false;
col[sta[top]]=scc;
scccost[scc]+=cost[sta[top]];
}while(sta[top]!=u);
}
return;
}*/
inline void tarjan(int u)
{
dfn[u]=low[u]=++dep;
sta[top++]=u;
instack[u]=true;
for(int i=hd[u];~i;i=E[i].nxt)
{
reg int v=E[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++scc;
do
{
--top;
instack[sta[top]]=false;
col[sta[top]]=scc;
scccost[scc]+=cost[sta[top]];
}while(u!=sta[top]);
}
return;
}
struct Node
{
int u,d;
inline bool operator < (const Node &nt) const
{
return nt.d>d;
}
};
int dis[MaxN];
bool vis[MaxN];
bool isbar[MaxN];
inline void dijkstra(int s)
{
priority_queue<Node> Q;
Q.push((Node){s,scccost[s]});
memset(dis,0xc0,sizeof dis);dis[s]=scccost[s];
while(!Q.empty())
{
reg int u=Q.top().u;Q.pop();
if(vis[u])
continue;
vis[u]=true;
for(int i=nhd[u];~i;i=nE[i].nxt)
{
reg int v=nE[i].to;
if(dis[v]<dis[u]+scccost[v])
{
dis[v]=dis[u]+scccost[v];
Q.push((Node){v,dis[v]});
}
}
}
return;
}
int dp[MaxN];
inline int dfs(int u,int fa)
{
if(dp[u]!=-1)
return dp[u];
for(int i=nhd[u];~i;i=nE[i].nxt)
{
reg int v=nE[i].to;
if(v==fa)
continue;
dp[u]=max(dp[u],dfs(v,u));
}
if(dp[u]==-1&&!isbar[u])
return -1;
if(dp[u]==-1)
dp[u]=0;
dp[u]+=scccost[u];
return dp[u];
}
signed main(void)
{
memset(hd,-1,sizeof hd);
memset(nhd,-1,sizeof nhd);
memset(dp,-1,sizeof dp);
cin>>n>>m;
reg int u,v;
int s,p;
for(int i=1;i<=m;++i)
{
read(u);read(v);
adde(u,v);
}
for(int i=1;i<=n;++i)
read(cost[i]);
cin>>s>>p;
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i);
{
reg int t;
for(int i=1;i<=p;++i)
read(t),bar.push_back(t),isbar[col[t]]=true;
}
/*
for(int i=1;i<=n;++i)
{
printf("Node %d in color %d scccost %d\n",i,
col[i],scccost[col[i]]);
}
*/
for(int u=1;u<=n;++u)
for(int i=hd[u];~i;i=E[i].nxt)
{
reg int v=E[i].to;
if(col[u]==col[v])
continue;
nadde(col[u],col[v]);
}
/*
dijkstra(col[s]);
reg int ans=0;
for(int i=0;i<(int)bar.size();++i)
ans=max(ans,dis[col[bar[i]]]);
printf("%lld\n",ans);
*/
cout<<dfs(col[s],0)<<endl;
return 0;
}原文：https://www.cnblogs.com/chinesepikaync/p/12437345.html