我们要求 \(1 \to A \to B \to C \to D \to 1\) 的点权和最大值，直接暴力枚举 \(4\) 个点 \(\mathcal {O(n^4)}\) 肯定是不行的。但是观察到前两个点与后两个点是对称的，于是我们可以枚举两组点进行配对，即 \(\text {Meet in the middle}\)。
首先考虑距离的限制条件，我们可以使用 \(\text {bfs}\) \(\mathcal {O(n^2)}\) 的预处理出两点之间的最短路 \(dis_{i,j}\)（边权都为 \(1\)）。
接着就是折半的预处理。记 \(f_{i,j}\) 表示从 \(1 \to i \to j\) 的最大点权和，且要满足 \(dis_{1,i} , dis_{i,j} \leq k\)，不满足就初始化为 \(\text{-inf}\)。直接 \(\mathcal {O(n^2)}\) 枚举两个点就行了。同时对于每个点，求出一个 \(lst_i\) 表示所有 \(f_{j,i}\) 中的最大值是从哪个点转移过来的。
于是我们就可以考虑枚举两个中间点 \(B,C\)，更新答案。但是我们会发现：在统计时有可能 \(B\) 的 \(lst_B\) 与另外两个点重复了，而题目又要求访问四个不同的景点，这样就寄了。
所以，我们不能只求出每个店的最大 \(f\) 值，还需要记录次大，次次大，以防重复的情况。这样在更新时判一下重复就行了。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,vis[2505];
int dis[2505][2505];
ll a[2505],f[2505][2505],ans;
int lst[2505][5];//1 st 2 nd 3 rd
int head[2505],cnt;
struct edge{
int u,v,nxt;
}e[200005];
void add(int u,int v){
e[++cnt].v=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
queue<int>q;
void bfs(int now){
for(int i=1;i<=n;++i)vis[i]=0,dis[now][i]=1e9;
dis[now][now]=0;
while(!q.empty())q.pop();
q.push(now);
while(!q.empty()){
int u=q.front();
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[now][v]>dis[now][u]+1)dis[now][v]=dis[now][u]+1;//更新最短路
q.push(v);
}
}
}
int main(){
cin>>n>>m>>k;++k;
for(int i=2;i<=n;++i)scanf("%lld",&a[i]);
for(int i=1;i<=m;++i){
int aa,bb;
scanf("%d%d",&aa,&bb);
add(aa,bb);
add(bb,aa);
}
for(int i=1;i<=n;++i)bfs(i);
for(int i=2;i<=n;++i){
for(int j=2;j<=n;++j){
f[i][j]=-1e18;
if(i==j)continue;
if(dis[i][j]<=k&&dis[1][i]<=k)f[i][j]=a[i]+a[j];//满足小于等于k再更新
// cout<<"1 -> "<<i<<" -> "<<j<<" "<<f[i][j]<<endl;
}
}
for(int i=2;i<=n;++i){
lst[i][1]=lst[i][2]=lst[i][3]=i;
for(int j=2;j<=n;++j){
if(i==j||dis[j][i]>k)continue;
if(f[j][i]>f[lst[i][1]][i]){//更新最大值
lst[i][3]=lst[i][2];
lst[i][2]=lst[i][1];
lst[i][1]=j;
}
else if(f[j][i]>f[lst[i][2]][i]){//更新次大值
lst[i][3]=lst[i][2];
lst[i][2]=j;
}
else if(f[j][i]>f[lst[i][3]][i])lst[i][3]=j;//更新次次大值
}
}
for(int i=2;i<=n;++i){
for(int j=2;j<=n;++j){
if(i==j||dis[i][j]>k)continue;
for(int pi=1;pi<=3;++pi){
for(int pj=1;pj<=3;++pj){
if(lst[i][pi]!=j&&lst[i][pi]!=lst[j][pj]&&lst[j][pj]!=i){//不能选重复的点
ans=max(ans,f[lst[i][pi]][i]+f[lst[j][pj]][j]);
}
}
}
}
}
cout<<ans;
return 0;
}