本题核心：Tarjan和最长路
这次改一下题解风格，先不放AC代码 （因为实在是太长了）
（哦对了）
先放上程序“缩略图”：
你看这个数组个数，你看这个过程（void）个数， （你看这个好看的马蜂） 是不是有点头大
不急，我们就按照我代码中一部分一部分来讲——
前置芝士：
- 邻接表存储/遍历（如果你这个都不会的话做这种综合大题有点早……先好好学图论吧）
- SPFA跑最长路（其实改个符号就好，没有必要建负权边跑最短路）
- Tarjan缩点（不会的同学先学好Tarjan再来做这道题哦，Tarjan练习题）
OK，现在假设上面的东西你都会，那么正式开始讲解：
再补充一句：这道题确实是道好题，我的题解会讲的很详细，如果你很想理解，做出这道题，最好耐心看完。如果没有耐心，吃亏的可不是我。
1.邻接表存储
这里我们用两个过程来存，一个add（存无边权的图），一个build（有边权）
先放上代码，等会就知道为什么要用两个了
void add(int u,int v)
{
cnt++;
e[cnt].to=v;
e[cnt].next=hd[u];
hd[u]=cnt;
} void build(int u,int v,int w)
{
cnt++;
e[cnt].to=v;
e[cnt].val=w;
e[cnt].next=hd[u];
hd[u]=cnt;
}2.输入部分
这道题的输入数据还是比较麻烦的
首先用数组存一下每条边的起点终点
等等，为什么要用数组存呢，直接输入不行吗
自己先想一下，虽然我一开始也没想到
这倒跟建边没什么关系
我们这么做主要是为了后面服务的
因为后面我们要用Tarjan缩点，缩完点以后有可能你一开始输入的那组边“就是一个点了”
不用数组存一下的话无法进行后续操作了
如果不理解的话就先搁着，后头主函数和Tarjan中会详细讲解然后再输入s，p
再输入每个酒吧，这个是为了最后遍历一遍dis[酒吧]所服务的。
当然你也可以在main中输入，省掉一个存酒吧位置的数组
等会详细说
代码就长这样：
void readln()
{
clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d%d",&s,&p);
for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
}u,v,w表示边起点，终点，点权的数组 bar是酒吧的英文，表示酒吧位置
眼尖的同学这时候要问了：clear是个什么东西
放心这次没 开挂 使用stl，这是我手写的一个清空数组的函数
长这样：
void clear()
{
cnt=0;
memset(e,0,sizeof(e));
memset(hd,0,sizeof(hd));
}对邻接表很熟悉的同学一看就懂：这是清空邻接表的操作啊（cnt归零，hd清零，边表也清零）
这里教大家一种memset的用法（我也是从楼下大佬中找的）
memset(结构体名字，值，sizeof(结构体名字))
这样可以直接清空（赋值）一个结构体哦
前提是你结构体中的类型要统一，比如说都是int
3.Tarjan缩点
void Tarjan(int x)
{
dfn[x]=low[x]=++total;
stk[++top]=x;vis[x]=true;
for(int i=hd[x];i;i=e[i].next)
{
int t=e[i].to;
if(!dfn[t])
{
Tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(vis[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])
{
tot++;
do{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
g[tp]=tot;
}while(stk[top--]!=x);
}
}基本就是标准Tarjan，我讲下不一样的地方吧：
tot++;
do{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
g[tp]=tot;
}while(stk[top--]!=x);这里我是用的数组模拟栈，首先int tp=stk[top]取出栈顶
sum表示缩完点后这个点的点权
不是很懂Tarjan的好好理解下Tarjan弹栈的部分再看这里就懂了
懂Tarjan的模拟一下应该就懂了，每次弹栈时，所有被弹出的点都是缩完点后的一个点
即sum[tot]+=w[tp]，缩完点后的点权+=原点权
很好理解吧
不懂的说明你对Tarjan还是理解不到位……这篇题解不是讲Tarjan的，楼下大佬应该有详细讲解。
然后vis[tp]=false表示tp已经出栈
g表示缩完点后每个点在哪个点中
即g[tp]=tot，tp这个点在缩完点后的第tot个点里
然后用栈顶和x比较，标准Tarjan操作
stk[top--]就相当于pop弹栈了大家应该都看懂了吧
那现在我们就已经缩好点了，g已经记录好了，sum也记录好每个新点的点权了
5.先来看下主函数
int main()
{
readln();
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
clear();
for(int i=1;i<=m;i++)
if(g[u[i]]!=g[v[i]])
build(g[u[i]],g[v[i]],sum[g[v[i]]]);
Spfa(s);
for(int i=1;i<=p;i++)
ans=max(ans,dis[g[bar[i]]]);
printf("%d",ans);
return 0;
}首先readln输入，就是第二部分（P党转来的我喜欢用readln嘿嘿）
然后标准Tarjan，if(!dfn[i]) Tarjan(i);
---(这里也是听别的大佬说的，Tarjan首字母最好大写，避免一些神奇的错误)
这时候clear就有用了，因为我们之前add建的图是为了Tarjan缩点用的，现在缩好点了那张图就没用了！我们没有必要新开一个结构体，反而浪费很多内存，把刚刚的图clear一下就好了
然后我们遍历每一条输入的边，这个时候之前的u,v数组就有用了！我们通过判断u[i],v[i]是否在一个新点里，如果不在的话就build一条新边，这样就能建一个缩完点后的图
注意build：起点是u[i]所在的缩点，终点是v[i]所在的缩点（如果u[i]和v[i]在一个缩点里就不会执行build了），边权是v[i]所在缩点的点权（sum）！！！
这样，这张新图就表明：从U走到V可以抢劫W的钱，钱数当然是缩点点权啊
没问题
吧？
有点问题的哦：相信不少同学也看出来了——那你这样每次把边权设置为后头那个缩点的点权，前头那个点被冷落了，点权不就没用了吗？
能想到这，恭喜你你理解这道题了
不过这个问题确实存在，我们的解决方案也很简单粗暴
直
接
来
看
6.Spfa跑最长路
正如一开始所说，我就是改了个符号，没有建负边权跑最短路，所以这一部分也是非常好理解的啦
直接上代码咯，spfa板子
void Spfa(int s)
{
for(int i=1;i<=tot;i++) dis[i]=0;
int gs=g[s];
q.push(gs);
vis[gs]=true;
dis[gs]=sum[gs];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=hd[h];i;i=e[i].next)
{
int t=e[i].to;
if(dis[t]<dis[h]+e[i].val)最短路中这里是>号，改成<号就是最长路咯
{
dis[t]=dis[h]+e[i].val;
if(!vis[t])
{
q.push(t);
vis[t]=true;
}
}
}
}
}
一看这个鬼畜的大括号就是spfa hhhhhhhh我们来解决刚刚的问题，起点的点权怎么办
你会发现，spfa又不完全是板子，我改了几个地方：
int gs=g[s];
q.push(gs);
vis[gs]=true;
dis[gs]=sum[gs];起点不是s了，而是g[s]，dis[起点]也不是0了
为什么呢？
你先想一下
——
——
——
想不出来？缩点是干啥用的来着？
——
——
——
想出来了吧：
我们刚刚build建的图是一张缩完点后的缩点图，所以我们push起点的时候当然是push缩完点后s所在的点啊
为什么呢？万一s本身就在一个环里，push（s)的话问题就大了
所以我们把起点一律改成g[s]来操作
并且，我们把起点的dis值直接加上点权，这样就不会漏掉起点点权了
而且放心，一开始更改dis值不会对后续松弛操作造成无法更改的影响，毕竟这是最长路
然后
然后
这道题就没什么可讲的了吧
最后再处理完主函数中这一部分：
for(int i=1;i<=p;i++)
ans=max(ans,dis[g[bar[i]]]);
printf("%d",ans);
return 0;最后还是放上完整AC代码吧：
#include<queue>
#include<cstdio>
#include<cstring>
#define N 500005
using namespace std;
struct edge{
int to,val,next;
} e[N];
int m,n,p,s,cnt,g[N],u[N],v[N],w[N],hd[N],bar[N],dis[N],dfn[N],low[N],stk[N],sum[N];
bool vis[N];
queue <int> q;
int ans=0,top=0,tot=0,total=0;
inline int min(int a,int b)
{return a<b?a:b;}
void add(int u,int v)
{
cnt++;
e[cnt].to=v;
e[cnt].next=hd[u];
hd[u]=cnt;
}
void build(int u,int v,int w)
{
cnt++;
e[cnt].to=v;
e[cnt].val=w;
e[cnt].next=hd[u];
hd[u]=cnt;
}
void clear()
{
cnt=0;
memset(e,0,sizeof(e));
memset(hd,0,sizeof(hd));
}
void readln()
{
clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d%d",&s,&p);
for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
}
void Tarjan(int x)
{
dfn[x]=low[x]=++total;
stk[++top]=x;vis[x]=true;
for(int i=hd[x];i;i=e[i].next)
{
int t=e[i].to;
if(!dfn[t])
{
Tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(vis[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])
{
tot++;
do{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
g[tp]=tot;
}while(stk[top--]!=x);
}
}
void Spfa(int s)
{
for(int i=1;i<=tot;i++) dis[i]=0;
int gs=g[s];
q.push(gs);
vis[gs]=true;
dis[gs]=sum[gs];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=hd[h];i;i=e[i].next)
{
int t=e[i].to;
if(dis[t]<dis[h]+e[i].val)
{
dis[t]=dis[h]+e[i].val;
if(!vis[t])
{
q.push(t);
vis[t]=true;
}
}
}
}
}
int main()
{
readln();
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
clear();
for(int i=1;i<=m;i++)
if(g[u[i]]!=g[v[i]])
build(g[u[i]],g[v[i]],sum[g[v[i]]]);
Spfa(s);
for(int i=1;i<=p;i++)
ans=max(ans,dis[g[bar[i]]]);
printf("%d",ans);
return 0;
}完结撒花！