// 多起点最短路+set优选 BFS 算法 O(n^2*3^3)
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rop(i,l,r) for(int i=l;i>=r;--i)
#define ll long long
using namespace std;

const int N=2505;
vector<int> e[N];
ll w[N],ans;
int n,m,k,d[N][N];
set<pair<ll,ll>> st[N];

void bfs(int s,int *d){
  rep(i,1,n) d[i]=2e9; d[s]=0;
  queue<int> q; q.push(s);
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(auto v:e[u]){
      if(d[v]>d[u]+1) d[v]=d[u]+1,q.push(v);
    }
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&k);
  rep(i,2,n) scanf("%lld",&w[i]);
  rep(i,1,m){
    int u,v; scanf("%d%d",&u,&v);
    e[u].push_back(v); e[v].push_back(u);
  }
  
  rep(i,1,n) bfs(i,d[i]); //预处理每个点的最短路
  
  rep(i,2,n) rep(j,2,n){ //预处理每个点的前3大可达点
    if(j==i) continue;
    if(d[i][j]<=k+1&&d[1][j]<=k+1) st[i].insert({w[j],j}); //如果i通过j可达1，就记录点j
    if(st[i].size()>3) st[i].erase(st[i].begin()); //保留i可达1的前3大点权
  }
  rep(b,2,n) rep(c,2,n) if(b!=c&&d[b][c]<=k+1){ //如果b、c不同且可达
    for(auto [wa,a]:st[b]) if(a!=c){            //如果b的可达点不是c
      for(auto [wd,d]:st[c]) if(d!=b&&d!=a){    //如果c的可达点不是b也不是a
        ans=max(ans,w[b]+w[c]+wa+wd);           //更新路径1-a-b-c-d-1的点权和
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}

暴力解法（60分）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2500+10;
LL a[N];
int dis[N][N];
int main()
{
    //freopen("a.in","r",stdin);
    int n,m,K;scanf("%d%d%d",&n,&m,&K);
    a[0]=0;for(int i=2;i<=n;i++)scanf("%lld",&a[i]);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        dis[x][y]=dis[y][x]=1;
    }
    
    // Floyd算法求全源最短路
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)if(i!=k)
            for(int j=1;j<=n;j++)if(j!=i && j!=k)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    
    LL ans=0;
    // 枚举四个不同的点i1,i2,i3,i4，满足从1出发到i1、i1到i2、i2到i3、i3到i4、i4到1的距离均<=K+1（注意K+1可能是题目中的步数限制）
    for(int i1=2;i1<=n;i1++)if(dis[1][i1]<=K+1)
        for(int i2=2;i2<=n;i2++)if(i2!=i1 && dis[i1][i2]<=K+1)
            for(int i3=2;i3<=n;i3++)if(i3!=i1 && i3!=i2 && dis[i2][i3]<=K+1)
                for(int i4=2;i4<=n;i4++)if(i4!=i1 && i4!=i2 && i4!=3 && dis[i3][i4]<=K+1 && dis[i4][1]<=K+1) // 注意原代码中i4!=3可能是笔误，需确认
                    ans=max(ans,a[i1]+a[i2]+a[i3]+a[i4]);
    printf("%lld",ans);
    return 0;
}

优化解法（标称）

#include <bits/stdc++.h>
#define LL long long
using namespace std;const int N=2505;
int n,m,K;LL a[N];bool vis[N][N];int dis[N][N];vector<int>G[N],G2[N];
bool cmp(int x,int y){return a[x]>a[y];}
void init()
{
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        dis[i][i]=0;
        queue<int>q;q.push(i);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            if(dis[i][x]>K)continue; // BFS求从i出发距离<=K的节点
            for(int y:G[x])
            {
                if(dis[i][y]>dis[i][x]+1)
                {
                    dis[i][y]=dis[i][x]+1;
                    vis[i][y]=true;
                    q.push(y);
                }
            } // 记录i到j的距离<=K的关系
        }
    }
    // 对每个节点i，收集与其距离<=K且能到达1的节点，取前2大的a值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)if(i!=j && vis[i][j] && vis[j][1])G2[i].push_back(j);
        sort(G2[i].begin(),G2[i].end(),cmp); // 按a值从大到小排序取前2
        while(G2[i].size()>2)G2[i].pop_back();
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    scanf("%d%d%d",&n,&m,&K);
    a[0]=0;for(int i=2;i<=n;i++)scanf("%lld",&a[i]); // 输入节点a值（假设节点2..n有价值）
    for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);} // 建图
    init(); // 预处理距离和候选节点
    LL ans=0; // 枚举两个节点i,j，分别取其前2大候选节点，求四者之和的最大值
    for(int i=2;i<=n;i++)
        for(int j=i+1;j<=n;j++)if(vis[i][j]){
            for(int i1:G2[i])if(i!=i1){
                for(int j1:G2[j])if(j1!=i && j1!=i1){
                    ans=max(ans,a[i]+a[j]+a[i1]+a[j1]);
                }
            }
        }printf("%lld\n",ans); // 输出最大和
    return 0;
}