这份代码在你谷上过了，但 infoj 上 WA 了一个点。

大体思路是先跑 $n$ 次 BFS，把每个点的能够连到的点记在 vector 里，然后记 $f[i][j]$ 为已经经过了 $i$ 个不同城市的最大权值和，然后一个 deque 记这个最大权值和来自哪些城市（用这个来判重）,然后该怎么 dp 怎么 dp，具体式子看代码吧。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 2500 + 5;
const int MAXM = 1e4 + 5;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll INCF = 0xcfcfcfcfcfcfcfcf;

ll inpt() {
	ll x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-')
		f = -1, ch = getchar();
	do {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, m, k;
ll w[MAXN];

struct Edge {
	int hd[MAXN];
	int nxt[MAXM << 1], to[MAXM << 1];
	int tot = 0;
	
	void Add(int x, int y) {
		nxt[++tot] = hd[x];
		hd[x] = tot;
		to[tot] = y;
	}
}e;

vector<int> con[MAXN];//可到达
bool vis[MAXN];
void bfs(int s) {
	memset(vis, false, sizeof(vis));
	vis[s] = true;
	deque< pair<int, int> > q;
	q.push_back({s, -1});
	
	while(q.size()) {
		int x = q.front().first, d = q.front().second;
		q.pop_front();
		
		if(x != s)
			con[s].push_back(x);
		
		if(d == k)
			continue;
		
		for(int i = e.hd[x]; i; i = e.nxt[i]) {
			int y = e.to[i];
			if(vis[y])
				continue;
			
			q.push_back({y, d + 1});
			vis[y] = true;
		}
	}
}

ll f[10][MAXN];
deque<int> g[10][MAXN];

int main()
{
	freopen("holiday.in", "r", stdin);
	freopen("holiday.out", "w", stdout);
	
	n = inpt(), m = inpt(), k = inpt();
	for(int i = 2; i <= n; ++i)
		w[i] = inpt();
	for(int i = 1; i <= m; ++i) {
		int x = inpt(), y = inpt();
		
		e.Add(x, y);
		e.Add(y, x);
	}
	
	for(int i = 1; i <= n; ++i)
		bfs(i);
	
	memset(f, 0xcf, sizeof(f));
	f[0][1] = 0;
	g[0][1].push_back(1);
	
	for(int i = 1; i <= 5; ++i) {
		for(int j = 1; j <= n; ++j) {
			for(auto it : con[j]) {
				bool flag = false;
				for(auto vised : g[i - 1][it])
					if(j == vised && j != 1)
						flag = true;
				if(flag)
					continue;
				
				if(f[i - 1][it] + w[j] > f[i][j]) {
					f[i][j] = f[i - 1][it] + w[j];
					g[i][j] = g[i - 1][it];
				}
			}
			
			g[i][j].push_back(j);
		}
	}
	
	printf("%lld", f[5][1]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}