蒟蒻只会写暴力，写了个贪心搜索

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ull unsigned long long
#define cant(A,B) (turn[s[A].index][s[B].index]>k)
#define TEST_FLOYD for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cerr<<turn[i][j]<<" ";cerr<<endl;}
const int maxn=2501,inf=2<<14;
struct SIGHT
{
	int index;
	ull weigh;
	static bool cmp(SIGHT a,SIGHT b)
	{
		return a.weigh>b.weigh;
	}
};
vector<SIGHT> s;
int turn[maxn][maxn],n,m,k;
bool vis[maxn],found=false;
ull ans=0;
void dfs(ull score,int step,int fa)
{
	if(found)return;
	if(step==4&&turn[fa][1]<=k)
	{
		ans=score,found=true;
	}
//	cerr<<endl<<"step== "<<step<<" ";
	for(int i=0;i<s.size();i++)
	{
		if((!vis[s[i].index])&&turn[fa][s[i].index]<=k)
		{
			vis[s[i].index]=true;
//			cerr<<s[i].index<<" " ;
			dfs(score+s[i].weigh,step+1,s[i].index);
			vis[s[i].index]=false;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
//	freopen("holiday.in","r",stdin),freopen("holiday.out","w",stdout);
	int a,b;
	cin>>n>>m>>k;
	//init for Floyd
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)turn[i][j]=inf;
	for(int i=1;i<=n;i++)turn[i][i]=0;
	
	ull w;
	for(int i=2;i<=n;i++)
	{
		cin>>w;
		s.push_back((SIGHT){i,w});
	}
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		turn[a][b]=turn[b][a]=1;
	}
	//Floyd
	for(int K=1;K<=n;K++)
	{
		for(int I=1;I<=n;I++)
		{
			for(int J=1;J<=n;J++)
			{
				turn[I][J]=min(turn[I][K]+turn[K][J],turn[I][J]);
			}
		}
	}
	++k;
	
	sort(s.begin(),s.end(),SIGHT::cmp);
	dfs(0,0,1);
	cout<<ans<<endl;
}