题意在这里。
分析题目发现这是个典型的缩点题：每一个强连通分量里面的点可以完全视作是同一个点。
之后再用SPFA求出最长路即可。（方法十分巧妙，是把所有边的边权都变成负的，然后求最短路，最后再把它们变回正的）
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
using namespace std;
const int N = 500005;
struct Edge
{
int v,next;
}e[N],e1[N];
int front[N],front1[N], cnt = 0, cnt1 = 0;
int dfn[N],low[N],stk[N],co[N],dis[N],num[N];
bool instk[N],isbar[N],bb[N],ins[N];
int tp = 0, tot = 0, t = 0;
int n,m;
int val[N],v[N];
int s,p;
void AddEdge(int u,int v)
{
e[++cnt].v = v;
e[cnt].next = front[u];
front[u]= cnt;
}
void AddEdge1(int u,int v)
{
e1[++cnt1].v = v;
e1[cnt1].next = front1[u];
front1[u] = cnt1;
}
void tarjan(int now)
{
dfn[now] = low[now] = ++t;
instk[now] = true;
stk[++tp] = now;
for (int i = front[now]; i; i = e[i].next)
{
int xx = e[i].v;
if (!dfn[xx])
{
tarjan(xx);
low[now] = min(low[now],low[xx]);
}
else if (instk[xx])
{
low[now] = min(low[now],dfn[xx]);
}
}
if(dfn[now] == low[now])
{
tot++;
while(stk[tp + 1] != now)
{
int xx = stk[tp];
instk[xx] = false;
tp--;
co[xx] = tot;
if (isbar[xx]) bb[tot] = true;
v[tot] += val[xx];
num[tot] = xx;
}
}
}
void spfa()
{
queue<int> Q;
Q.push(co[s]);
memset(ins,false,sizeof ins);
memset(dis, 0x3f, sizeof dis);
dis[co[s]] = v[co[s]];
int h;
while(!Q.empty())
{
h = Q.front(); Q.pop();
ins[h] = false;
for (int i = front1[h]; i; i = e1[i].next)
{
int xx = e1[i].v;
if (dis[xx] > dis[h] + v[xx])
{
dis[xx] = dis[h] + v[xx];
if (!ins[xx])
{
ins[xx] = true;
Q.push(xx);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1; i <= m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
AddEdge(a,b);
}
for (int i = 1; i <= n; i++)
{
scanf("%d",&val[i]);
}
scanf("%d%d",&s,&p);
for (int i = 1; i <= p; i++)
{
int a;
scanf("%d",&a);
isbar[a] = true;
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i]) tarjan(i);
}
for (int k = 1; k <= n; k++)
{
for (int i = front[k]; i; i = e[i].next)
{
int xx = e[i].v;
if (co[k] != co[xx]) AddEdge1(co[k], co[xx]);
}
}
for (int i = 1; i <= tot; i++) v[i] = -v[i];
spfa();
int ans = 0;
for (int i = 1; i <= tot; i++)
{
if(bb[i] && ans < -dis[i]) ans = -dis[i];
}
printf("%d\n",ans);
return 0;
}