Description：

在每个路口都设立了一个取款机。酒吧也都设在路口，并不是每个路口都设有酒吧。从市中心出发，沿着单向道路行驶，抢劫所有他途径的 $ ATM $ 机。已知了每个 $ ATM $ 机中可以掠取的现金数额。计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。

$1\le n\le 500010$

Solution：

$tarjan$ 缩点，然后在拓扑排序上 $dp$ ，注意初始化。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int val[MAXN];

int st;

bool tag[MAXN];

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool v[MAXN];

int scc = 0,ins[MAXN];

vector<int> g[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

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

	{

		int t;

		++scc;

		do

		{

			t = s.top();s.pop();

			v[t] = false;ins[t] = scc;

		}while(t != k);

	}

	return;

}

int ind[MAXN];

int f[MAXN];

int cnt[MAXN];

bool flag[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&val[i]);

	}

	scanf("%d",&st);

	int p,x;

	scanf("%d",&p);

	memset(tag,false,sizeof(tag));

	for(int i = 1;i <= p;++i)

	{

		scanf("%d",&x);

		tag[x] = true;

	}

	for(int i = 1;i <= n;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	for(int k = 1;k <= n;++k)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(ins[k] != ins[e[i].to])

			{

				g[ins[e[i].to]].push_back(ins[k]);

				++ind[ins[k]];

			}

		}

	}

	memset(f,0xc0,sizeof(f));

	for(int i = 1;i <= n;++i)

	{

		cnt[ins[i]] += val[i];

		flag[ins[i]] |= tag[i];

	}

	for(int i = 1;i <= scc;++i)

	{

		if(flag[i])f[i] = cnt[i];

	}

	queue<int> q;

	for(int i = 1;i <= scc;++i)

	{

		if(ind[i] == 0)

		{

			q.push(i);

		}

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

		{

			if(f[*it] < f[k] + cnt[*it])

			{

				f[*it] = f[k] + cnt[*it];

			}

			--ind[*it];

			if(ind[*it] == 0)

			{

				q.push(*it);

			}

		}

	}

	cout << f[ins[st]] << endl; 

	return 0;

}