RT 思路跟第3篇题解差不多

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2505;
int n,m,k,a[N],ans=0,b[N],lt[N][N];
struct zt{
    int now,tot;
};
struct node{
    int bh,z;
    bool operator<(const node b)const{
        return z<b.z;
    }
    bool operator>(const node b)const{
        return z>b.z;
    }
};
vector<int>s[N];
set<node>t[N];
void bfs(int x){
    queue<zt>q;
    int bj[N]={};
    q.push({x,-1});
    bj[x]=1;
    while(q.size()){
        zt o=q.front();
        q.pop();    lt[x][o.now]=lt[o.now][x]=1;
        if(o.tot+1>k)continue;
    
        for(int i=0;i<s[o.now].size();i++){
            int j=s[o.now][i];
            if(bj[j])continue;
            if(b[j]&&j!=1)t[x].insert({j,a[j]});
            if(t[x].size()>3){
                t[x].erase(*t[x].begin());
            }
            q.push({j,o.tot+1}),bj[j]=1;
        }
    }
}
void bfs1(){
    queue<zt>q;
    int bj[N]={};
    q.push({1,-1});
    bj[1]=1;
    while(q.size()){
        zt w=q.front();
        b[w.now]=1;
        q.pop();
        for(int i=0;i<s[w.now].size();i++){
            int j=s[w.now][i];
            if(!bj[j]&&w.tot+1<=k){
                bj[j]=1;
                q.push({j,w.tot+1});
            }
        }
    }
}
int bj[N];
bool dfs(int tt,int tot,int mb){
    queue<pair<int,int> > q;
    q.push({-1,tt});
    bj[tt]=1;
    while(q.size()){
        pair<int,int>now=q.front();
        q.pop();
        if(now.second==mb)return true;
        for(int i=0;i<s[now.second].size();i++){
            int j=s[now.second][i];
            if(bj[j])continue;
            if(now.first+1<=k){
                bj[j]=1;
                q.push({now.first+1,j});
            }
        }
    }
    return false;
}
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n-1;i++){
        cin>>a[i+1];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        s[u].push_back(v);
        s[v].push_back(u);
    }
    bfs1();
    for(int i=2;i<=n;i++){
        bfs(i);
    }
    int ans=0;
    for(int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            if(i==j)continue;
            if(!lt[i][j])continue;
            for(auto x:t[i]){
                for(auto y:t[j]){
                    if(x.bh!=y.bh&&x.bh!=i&&x.bh!=j&&y.bh!=i&&y.bh!=j){
                        ans=max(ans,a[i]+a[j]+x.z+y.z);
                    }
                    
                }
            }
        }
    }
    cout<<ans;
    return 0;
}