思路是bfs求每两点间距离，dp[i][j]表示第i个点选j时最大分数.

#include<bits/stdc++.h>
using namespace std;
vector<int>a[2501],b[2501],f[5][2501];
int c[2501];
long long sc[2501],dp[5][2501];
int main() {
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2; i<=n; ++i)
		scanf("%lld",&sc[i]);
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1; i<=n; ++i) {
		memset(c,0,sizeof(c));
		queue<int>d;
		d.push(i);
		while(!d.empty()) {
			int w=d.front();
			d.pop();
			for(int j=0; j<a[w].size(); ++j)
				if(a[w][j]!=i&&!c[a[w][j]]) {
					c[a[w][j]]=c[w]+1;
					if(c[a[w][j]]<=k+1) b[i].push_back(a[w][j]);
					d.push(a[w][j]);
				}
		}
	}
	for(int i=0; i<b[1].size(); ++i) {
		dp[1][b[1][i]]=sc[b[1][i]];
		f[1][b[1][i]].push_back(b[1][i]);
	}
	for(int i=2; i<=4; ++i)
		for(int j=2; j<=n; ++j) {
			int p=0;
			for(int q=0; q<b[j].size(); ++q) {
				int k=b[j][q];
				if(k==1||!f[i-1][k].size()) continue;
				bool o=0;
				for(int l=0; l<f[i-1][k].size()&&!o; ++l)
					if(f[i-1][k][l]==j) o=1;
				if(!o&&dp[i-1][k]+sc[j]>dp[i][j]) {
					dp[i][j]=dp[i-1][k]+sc[j];
					p=k;
				}
			}
			if(p) {
				for(int l=0; l<f[i-1][p].size(); ++l)
					f[i][j].push_back(f[i-1][p][l]);
				f[i][j].push_back(j);
			}
		}
	long long ans=0;
	for(int i=0; i<b[1].size(); ++i)
		ans=max(ans,dp[4][b[1][i]]);
	printf("%lld",ans);
	return 0;
}