我的赛时代码碾过了InfOJ与洛谷的民间数据，但感觉复杂度不对。做法是预处理全源最短路，然后建新图，最后dfs枚举四个点。

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const int N=2503,inf=1000000000;

int n,m,k;
long long p[N];
vector<int>e[N];

queue<int>q;
int dist[N][N];
bool vis[N];

vector<int>g[N];
long long f[N][4];

void dfs(int u,int dep,long long sum)
{
	vis[u]=true;
	sum+=p[u];
	f[u][dep]=sum;
	if(dep==3)
	{
		vis[u]=false;
		return;
	}
	
	for(int i=0,v,siz=g[u].size();i<siz;i++)
	{
		v=g[u][i];
		if(!vis[v] && f[v][dep+1]<sum+p[v])
			dfs(v,dep+1,sum);
	}
	vis[u]=false;
}

int main()
{
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)
				dist[i][j]=inf;
	for(int i=2;i<=n;i++)
		cin>>p[i];
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	k++;
	
	for(int s=1;s<=n;s++)
	{
		q.push(s);
		vis[s]=true;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			
			for(int i=0,v,siz=e[u].size();i<siz;i++)
			{
				v=e[u][i];
				if(!vis[v])
				{
					dist[s][v]=dist[s][u]+1;
					q.push(v);
					vis[v]=true;
				}
			}
		}
		
		memset(vis,0,sizeof vis);
	}
	
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(dist[i][j]<=k)
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
	
	vis[1]=true;
	for(int i=0,siz=g[1].size();i<siz;i++)
		dfs(g[1][i],0,0);
	
	long long ans=0;
	for(int i=0,siz=g[1].size();i<siz;i++)
	{
		ans=max(ans,f[g[1][i]][3]);
	}
	cout<<ans;
	
	return 0;
}