n^4爆搜过了求hack

#include <cstdio>
#include <vector>
#include <algorithm>
#define N 2510
int n,m,k;long long a[N],f[9],ans;
std::vector<int> e[N],g[N];
bool vis[N],home[N];
struct pair{int x,d;}q[N];
void bfs(int s)
{
	int head=0,tail=0;
	q[head++]=pair{s,k};
	vis[s]=true;
	while(head!=tail)
	{
		pair x=q[tail++];
		e[s].push_back(x.x);
		if(x.d>=0) for(auto i:g[x.x]) if(!vis[i])
		{
			vis[i]=true;
			q[head++]=pair{i,x.d-1};
		}
	}
}
void dfs2(int x,int dep,long long tmp)
{
	if(vis[x]||tmp+f[dep]<=ans) return;
	if(dep==0) {if(home[x]) ans=tmp; return;}
	vis[x]=true;
	for(auto i:e[x]) dfs2(i,dep-1,tmp+a[i]);
	vis[x]=false;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++) scanf("%lld",a+i);
	for(int i=0,u,v;i<m;i++) {scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u);}
	//预处理可达点 
	for(int i=1;i<=n;i++)
	{
		bfs(i);
		std::random_shuffle(e[i].begin(),e[i].end());
		for(auto j:e[i]) vis[j]=false;
	}
	//双向边预处理可达1点 
	for(auto j:e[1]) home[j]=true;
	//预处理前4大点
	for(int i=4;i>=1;i--)
	{
		for(int j=2;j<=n;j++) if(a[j]>a[f[i]]&&!vis[j]) f[i]=j;
		vis[f[i]]=true;
	}
	for(int i=1;i<=4;i++)
	{
		vis[f[i]]=false;
		f[i]=f[i-1]+a[f[i]];
	}
	//爆搜
	dfs2(1,4,0);
	printf("%lld",ans); 
}