记录编号	577284	评测结果	AAAAAAAAAWATATAWATTT
题目名称	3781.[CSP 2022S]假期计划	最终得分	65
用户昵称	HeSn	是否通过	未通过
代码语言	C++	运行时间	11.708 s
提交时间	2022-10-30 12:33:07	内存使用	75.10 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3010;
int n, m, k, a[MAXN], dis[MAXN][MAXN], dis1[MAXN];
int cs[MAXN], cs1[MAXN], cnt, cnt1, ans;
bool vis[MAXN];
vector<int> cd[MAXN];
signed main() {
 	freopen("csp2022_holiday.in", "r", stdin);
 	freopen("csp2022_holiday.out", "w", stdout);
	cin >> n >> m >> k;
	for(int i = 1; i < n; i ++) {
		cin >> a[i + 1];
	}
	for(int i = 1; i <= m; i ++) {
		int x, y;
		cin >> x >> y;
		cd[x].push_back(y);
		cd[y].push_back(x);
	}
	queue<int> q;
	q.push(1);
	memset(dis, 0x3f, sizeof(dis));
	dis[1][1] = -1;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for(int i = 0; i < cd[x].size(); i ++) {
			int u = cd[x][i];
			if(dis[1][u] > dis[1][x] + 1) {
				dis[1][u] = dis[1][x] + 1;
				if(!vis[u]) {
					vis[u] = 1;
					q.push(u);
				}
			}
		}
	}
	for(int i = 2; i <= n; i ++) {
		if(dis[1][i] <= k) {
			cs[++ cnt] = i;
		}
	}
	for(int i = 1; i <= cnt; i ++) {
		int x = cs[i];
		dis[x][x] = -1;
		q.push(x);
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			vis[u] = 0;
			for(int i = 0; i < cd[u].size(); i ++) {
				int v = cd[u][i];
				if(dis[x][v] > dis[x][u] + 1) {
					dis[x][v] = dis[x][u] + 1;
					if(!vis[v]) {
						vis[v] = 1;
						q.push(v);
					}
				}
			}
		}
	}
	for(int i = 1; i <= cnt; i ++) {
		cnt1 = 0;
		for(int j = 2; j <= n; j ++) {
			if(dis[cs[i]][j] <= k && j != cs[i]) {
				cs1[++ cnt1] = j;
			}
		}
		
		memset(dis1, 0x3f, sizeof(dis1));
		
		for(int j = i + 1; j <= cnt; j ++) {
			
			for(int l = 1; l <= cnt1; l ++) {
				
				int x = cs1[l];
				dis[x][x] = -1;
				q.push(x);
				while(!q.empty()) {
					int u = q.front();
					q.pop();
					vis[u] = 0;
					for(int i = 0; i < cd[u].size(); i ++) {
						int v = cd[u][i];
						if(dis[x][v] > dis[x][u] + 1) {
							dis[x][v] = dis[x][u] + 1;
							if(!vis[v]) {
								vis[v] = 1;
								q.push(v);
							}
						}
					}
				}
				int maxn = 0, num;
				for(int i1 = 2; i1 <= n; i1 ++) {
					if(i1 != cs[i] && i1 != cs[j] && i1 != cs1[l] && cs[j] != cs1[l]) {
						if(dis[x][i1] <= k && dis[cs[j]][i1] <= k) {
							if(a[i1] > maxn) {
								num = i1;
							}
							maxn = max(maxn, a[i1]);
						}
					}
				}
				if(num == cs1[l]) {
					continue;
				}
				ans = max(ans, maxn + a[cs[i]] + a[cs[j]] + a[cs1[l]]);
//				cout << cs[i] << ' ' << cs[j] << ' ' << cs1[l] << ' ' << num << ' ' << (num == cs1[l]) << ' ' << maxn + a[cs[i]] + a[cs[j]] + a[cs1[l]] << endl;
			}
		}
	}
	cout << ans;
	return 0;
}