这道题可以考察图论的掌握程度（算半道水题）
题目如下
输入
第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号
输出
输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
样例输入
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
样例输出
47
提示
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
题解
这道题考到了spfa和tarjan唯一需要考虑的地方是，当你tarjan一遍之后，你需要做缩点，那么缩点之后你要做的事是重建整张图，把同一强连通分量里的点缩到同一点，再次建边，然后就是裸SPFA的事情了(缩点的过程用并查集考虑)
下面贴出代码
#include<cstdio>
#include<cstring>
struct shit{
int aim;
int next;
int get;
bool use;
}e[];
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)
{
return x<y?x:y;
}
int point,head[],n,m,ass,cnt,stack[],low[],time[],a,b,T;
int father[],quq[],val[],d[],star,ans;
bool f[];
void fuck(int x,int y)
{
e[++point].aim=y;
e[point].get=x;
e[point].next=head[x];
head[x]=point;
}
void rebuild()
{
memset(head,,sizeof(head));
point=;
for(int i=;i<=m;i++)
if(father[e[i].get]==father[e[i].aim]);
else fuck(father[e[i].get],father[e[i].aim]);
}
void tarjan(int sb)
{
low[sb]=time[sb]=++T;
f[sb]=true;
stack[++ass]=sb;
for(int k=head[sb];k!=;k=e[k].next)
{
if(!time[e[k].aim])
{
tarjan(e[k].aim);
low[sb]=min(low[sb],low[e[k].aim]);
}
else if(f[e[k].aim])low[sb]=min(low[sb],time[e[k].aim]);
}
if(time[sb]==low[sb])
{
f[sb]=false;
while(stack[ass]!=sb)
{
val[sb]+=val[stack[ass]];
f[stack[ass]]=false;
father[stack[ass--]]=sb;
}
ass--;
}
}
void SPFA(int num)
{
memset(f,,sizeof(f));
star=,ass=;
quq[++star]=num,f[num]=true,d[num]=val[num];
while(star<=ass)
{
int u=quq[star++];
for(int k=head[u];k!=;k=e[k].next)
{
int v=e[k].aim;
if(d[u]+val[v]>d[v])
{
d[v]=d[u]+val[v];
if(f[v])continue;
quq[++ass]=v;
f[v]=true;
}
}
f[u]=false;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
fuck(a,b);
}
for(int i=;i<=n;i++)
{
father[i]=i;
scanf("%d",&val[i]);
}
for(int i=;i<=n;i++)if(!time[i])tarjan(i);
rebuild();
scanf("%d%d",&a,&b);
SPFA(father[a]);
for(int i=;i<=b;i++)
{
scanf("%d",&a);
ans=max(ans,d[father[a]]);
}
printf("%d",ans);
return ;
}