复杂度大概是$O(n^4)$的。

#include<bits/stdc++.h>
#define MAXN 2505
#define int long long
using namespace std;
int dis[MAXN][MAXN];
long long a[MAXN];
vector<int>G[MAXN];
vector<int>G2[MAXN];
int que[MAXN],head,tail;
long long n,m,k,ans;
signed main(){
    cin>>n>>m>>k;
    for(int i=2;n>=i;i++)cin>>a[i];
    int x,y;
    for(int i=0;m>i;i++){
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;n>=i;i++){//bfs求每个点k个转移内能到达的点。G2储存每个点能到达的点。
        dis[i][i]=0;
        tail=head=0;
        que[tail++]=i;
        while(tail>head){
            int x=que[head];head++;
            int l=G[x].size();
            for(int j=0;l>j;j++){
                if(dis[i][G[x][j]]||dis[i][x]>k)continue;
                dis[i][G[x][j]]=dis[i][x]+1;
                que[tail++]=G[x][j];
                if(i!=G[x][j])G2[i].push_back(G[x][j]);
            }
        }
    }
    int l=G2[1].size();
    for(int i=0;l>i;i++){//暴力枚举。
        for(int j=0;l>j;j++){
            if(i==j)continue;
            int x=G2[1][i],y=G2[1][j];
            int l1=G2[x].size(),l2=G2[y].size();
            for(int t=0;l1>t;t++){
                if(G2[x][t]==1||G2[x][t]==y||G2[x][t]==x)continue;
                for(int r=0;l2>r;r++){
                    if(G2[y][r]==1||G2[y][r]==x||G2[x][t]==G2[y][r]||G2[y][r]==y||!dis[G2[x][t]][G2[y][r]])continue;
                    ans=max(ans,a[x]+a[y]+a[G2[x][t]]+a[G2[y][r]]);
                }
            }
        }
    }
    cout<<ans;
    return 0;

}