思路是先处理出每个点经过k步能到达的点，然后枚举AB，把所有AB结果存下来（记为que并按AB权值和降序），最后从que中暴力选两组AB来判断合法算最大值。

我大胆猜了一个优化，最后枚举两组AB时，如果枚举第二组AB（记位置是fin）能更新答案，则最终答案选的两组AB在que中位置不后于fin。

我想知道能否可能构造数据使得枚举要跑满才能更新fin。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k;
ll a[2505];
vector<int> vc[2505];
vector<int> cnto[2505];
struct node{
	int u,lst;
	ll ans;
}que[10000005];
int tl;
struct nde{
	int u,dis;
	bool operator <(const nde &b)const{
		return dis>b.dis;
	}
};
priority_queue<nde> q;
int dss[2505];
void dijk(int s){
	for(int i = 1;i<=n;++i) dss[i] = 10000000;
	dss[s] = 0;
	q.push((nde){s,0});
	while(!q.empty()){
		int u = q.top().u,si = vc[u].size();q.pop();
		for(int i = 0;i<si;++i){
			int v = vc[u][i];
			if(dss[v] > dss[u]+1){
				dss[v] = dss[u]+1;
				q.push((nde){v,dss[v]}); 
			}
		}
	}
}
bool relto[2505][2505];
bool cmp(int x,int y){
	return a[x]>a[y];
}
bool cmp2(node x,node y){
	return x.ans > y.ans;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 2;i<=n;++i) scanf("%lld",a+i);
	int u,v;
	for(int i = 1;i<=m;++i){
		scanf("%d%d",&u,&v);
		vc[u].push_back(v),vc[v].push_back(u);
	}
	for(int i = 1;i<=n;++i){
		dijk(i);
		for(int j = 2;j<=n;++j){
			if(dss[j]<=k+1 && 1<=dss[j]) cnto[i].push_back(j),relto[i][j] = relto[j][i] = true;
		}
	}
	sort(cnto[1].begin(),cnto[1].end(),cmp);
	int si = cnto[1].size();
	for(int i = 0;i<si;++i){
		int st = cnto[1][i],ssii = cnto[st].size();
		for(int j = 0;j<ssii;++j){
			if(cnto[st][j] != 1) que[++tl] = (node){cnto[st][j],st,a[st]+a[cnto[st][j]]};
		}
	}
	sort(que+1,que+tl+1,cmp2);
	ll ans = 0;
	int fin = tl;
	for(int i = 1;i<=min(fin,tl);++i){
		for(int j = i+1;j<=min(fin,tl);++j){
			if(relto[que[i].u][que[j].u] && que[i].lst != que[j].lst && que[i].lst != que[j].u && que[j].lst != que[i].u) ans = max(ans,que[i].ans+que[j].ans),fin = j;
		}
	}
	printf("%lld",ans);
	return 0;
}