记录

思路和第一篇题解大概差不多

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=30010,M=200010;
int e[M],ne[M],h[N],idx;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int val[N],m,n,k,d[N],f[N][4]/*每个点权值前三大的可达的点*/;
bool can[N][N]/*换乘k次内可达的一对点*/,vis[N];
void gets(int s)
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > > d;//大根堆，放可达点的权值
	memset(vis,0,sizeof vis);
	queue<pair<int,int> > q;//bfs用的队列
	q.push(make_pair(s,0));
	while(!q.empty())
	{
		auto u=q.front();q.pop();
		if(u.second>k+1) break;
		//if(s!=u.first) can[s][u.first]=1;
		if(can[1][u.first]) d.push(make_pair(val[u.first],u.first));
		if(s!=u.first) can[s][u.first]=1;
		for(int i=h[u.first];~i;i=ne[i])
			if(!vis[e[i]]) 
				vis[e[i]]=1,q.push(make_pair(e[i],u.second+1));
	}
	for(int i=1;i<=3 && !d.empty();++i)
		f[s][i]=d.top().second,d.pop();
}
signed main()
{
	memset(h,-1,sizeof h);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=2;i<=n;++i) scanf("%lld",&val[i]);
	val[1]=-1000000000000000003;
	val[0]=-1000000000000000003;
	for(int i=1,x,y;i<=m;++i) scanf("%lld%lld",&x,&y),add(x,y),add(y,x);
	for(int i=1;i<=n;++i) gets(i);
	int ans=0;
	for(int b=2;b<=n;++b)
		for(int c=2;c<=n;++c)
			if(can[b][c])
				for(int i=1;i<=3;++i)
					for(int j=1;j<=3;++j)
						if(f[b][i]&&f[c][j]&&f[b][i]!=c&&f[b][i]!=b&&f[c][j]!=b&&f[c][j]!=c&&f[c][j]!=f[b][i])
							ans=max(ans,val[f[b][i]]+val[b]+val[c]+val[f[c][j]]);
	printf("%lld",ans);
	return 0;
}