正经题解

#include<bits/stdc++.h>
using namespace std;
const int N = 2505, M = 20005;
int n, m, k, cnt, head[N];
struct Edge {int to,next;} e[M];
long long w[N];
char di[N][N];
struct Node {int id; long long w;} wi[N][4];
bool cmpNode(const Node &a, const Node &b) { return a.w > b.w; }
void ad(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; }
int main(){
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++) cin>>w[i];
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        ad(x,y);
        ad(y,x);
    }
    for(int i=1;i<=n;i++){
        static int dis[N];
        for(int j=1;j<=n;j++) dis[j]=1000000000;
        queue<int> q;
        dis[i]=0;
        q.push(i);
        while(!q.empty()){
            int u=q.front(); q.pop();
            if(dis[u]>=k+1) continue;
            for(int t=head[u]; t; t=e[t].next){
                int v=e[t].to;
                if(dis[v]>dis[u]+1){
                    dis[v]=dis[u]+1;
                    di[i][v]=1;
                    if(di[1][v] && v!=1){
                        wi[i][3].id=v;
                        wi[i][3].w=w[v];
                        sort(wi[i], wi[i]+4, cmpNode);
                    }
                    q.push(v);
                }
            }
        }
    }
    long long ans=0;
    for(int b=2;b<=n;b++){
        for(int c=2;c<=n;c++){
            if(b==c || !di[b][c]) continue;
            for(int i=0;i<3;i++){
                int a = wi[b][i].id;
                if(!a) continue;
                for(int j=0;j<3;j++){
                    int d = wi[c][j].id;
                    if(!d) continue;
                    if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d){
                        long long s = w[a] + w[b] + w[c] + w[d];
                        if(s > ans) ans = s;
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}