首先先要看懂题目，大意就是找到四个不同景点，在满足每次到达景点的距离不超过$k+1$（就是题目中所说的k次通达）的情况下，使四个景点的分数总和最大。
还要注意这道题的输入里面有一个小坑，景点分数只有n-1个，所以要从2开始输入刚开始因为这个样例没过

---

暴力解法：

1.先通过BFS求解点之间的最短距离
2.直接四层循环枚举$A,B,C,D$，需要满足的条件是距离不超过$k+1$

---

正解：

思路

写完暴力后就要开始想如何优化这个四层循环，我们注意到其实没有必要枚举$D$，可以先预处理满足条件的$C$（我们称为候选点），这样复杂度降为$O(3n^3)$，那么同理，$A$也可以通过$B$的候选点来得到，这样复杂度就降为了$O(9n^2)$

解法：

1.跟暴力一样先BFS求点之间的最短距离
2.与暴力不同的是我们还要预处理$B$和$C$的候选点
3.循环遍历$B,C$，然后通过预处理好的候选点来求$A,D$，然后找最大值就行了

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3e3+5;
const int INF=2e9;
int n,m,k;
long long a[N];
vector<int>ve[N];//图
int dis[N][N];//距离

//求到每个景点的距离
void get_dis(){
    for(int i=1;i<=n;i++){
        queue<int>q;
        q.push(i);
        for(int j=1;j<=n;j++)dis[i][j]=INF;
        dis[i][i]=0;
        while(q.size()){
            int u=q.front();
            q.pop();
            for(auto v:ve[u]){
                if(dis[i][v]==INF){
                    dis[i][v]=dis[i][u]+1;
                    q.push(v);
                }
            }
        }
    }
}

//求B，C的候选景点从而省掉枚举A，D的时间
vector<int>cand[N];//记录候选景点
void get_cand(){
    for(int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            if(i==j)continue;
            if(dis[1][j]<=k && dis[i][j]<=k)
                cand[i].push_back(j);
        }
        sort(cand[i].begin(),cand[i].end(),[&](int x,int y){
            return a[x]>a[y];
        });
        if(cand[i].size()>3)cand[i].resize(3);
    }
}

int main(){
    cin>>n>>m>>k;
    k++;//方便后面判断
    for(int i=2;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }

    get_dis();
    get_cand();

    long long ans=0;
    //枚举B，C
    for(int b=2;b<=n;b++){
        for(int c=2;c<=n;c++){
            if(b==c)continue;
            if(dis[b][c]>k)continue;
            for(auto A:cand[b]){
                for(auto d:cand[c]){
                    //如果枚举的是相同点就跳过
                    if(A==b || A==c || A==d)continue;
                    if(b==c || b==d)continue;
                    if(c==d)continue;
                    ans=max(ans,a[A]+a[b]+a[c]+a[d]);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}