记录编号	601060	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3781.[CSP 2022S]假期计划	最终得分	100
用户昵称	Galaxy	是否通过	通过
代码语言	C++	运行时间	1.990 s
提交时间	2025-05-29 15:11:24	内存使用	21.78 MiB

#include <bits/stdc++.h>
namespace std{istream&operator>>(istream&is,__int128&n){string s;is>>s;n=0;for(char c:s)n=n*10+(c-'0');return is;}ostream&operator<<(ostream&os,__int128 n){if(!n){os<<'0';return os;}string s;while(n){s+=char('0'+n%10);n/=10;}reverse(s.begin(),s.end());os<<s;return os;}}
#define int long long

int n, m, k, a[3000], dis[2510][2510];
std::vector<int> G[3000], edge[2500];
struct nod {
	int dis, num;
	bool operator<(const nod &b) const {
		return dis > b.dis;
	}
};

void dijkstra(int st) {
	for (int i = 1; i <= n; i++) {
		dis[st][i] = 1e9;
	}

	std::priority_queue<nod> q;
	q.emplace(nod{0, st});

	while (!q.empty()) {
		nod head = q.top();
		q.pop();

		if (dis[st][head.num] < head.dis) {
			continue;
		}

		if (st != head.num) {
			edge[st].emplace_back(head.num);
		}

		dis[st][head.num] = head.dis;

		for (auto to : G[head.num]) {
			if (dis[st][to] > head.dis + 1 && head.dis + 1 <= k + 1) {
				dis[st][to] = head.dis + 1;
				q.emplace(nod{dis[st][to], to});
			}
		}
	}
}

bool cmp(int A, int B) {
	return a[A] > a[B];
}

int dist[2510][4], ans, tmp[2510];

int solve() {
	for (int i = 2; i <= n; i++) {
		int tot = 0;

		for (int j = 1; j <= n; j++) {
			tmp[j] = 0;
		}

		for (auto j : edge[i]) {
			if (j == 1 || j == i) {
				continue;
			}
			if (dis[1][j] < 1e9) {
				tmp[++tot] = j;
			}
		}

		std::sort(tmp + 1, tmp + 1 + tot, cmp);
		dist[i][1] = tmp[1], dist[i][2] = tmp[2], dist[i][3] = tmp[3];
	}

	for (int i = 2; i <= n; i++) {
		for (auto j : edge[i]) {
			if (j == 1) {
				continue;
			}

			for (int x = 1; x <= 3; x++) {
				for (int y = 1; y <= 3; y++) {
					if (dist[i][x] != j && dist[i][x] != dist[j][y] && dist[j][y] != i && i != j && dist[i][x] && dist[j][y]) {
						ans = std::max(ans, a[i] + a[j] + a[dist[i][x]] + a[dist[j][y]]);
					}
				}
			}
		}
	}
	return ans;
}

#undef int
int main() {
#define int long long
	std::cin.tie(nullptr)->sync_with_stdio(false);
	freopen("csp2022_holiday.in", "r", stdin);
	freopen("csp2022_holiday.out", "w", stdout);
	std::cin >> n >> m >> k;
	for (int i = 2; i <= n; i++) {
		std::cin >> a[i];
	}

	for (int i = 1; i <= m; i++) {
		int u, v;
		std::cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}

	for (int i = 1; i <= n; i++) {
		dijkstra(i);
	}

	std::cout << solve();
	return 0;
}