85pts

WA on #7 # 25 #34 #39 #45

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, m, k, a[2505], dis[2505][2505], ans, ci[2505], c[2505][6];
vector<int> g[20005];
queue<int > q;
struct W {
	int u;
	bool operator<(const W&x)const {
		return a[x.u] > a[u];
	}
};
priority_queue<W>qu;
signed main() {
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	cin >> n >> m >> k;
	k++;
	for (int i = 2; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		while (!q.empty()) q.pop();
		q.push(i);
		dis[i][i] = 0;
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int j = 0; j < g[now].size(); j++) {
				if (dis[i][now] + 1 < dis[i][g[now][j]]) {
					dis[i][g[now][j]] = dis[i][now] + 1;
					if (dis[i][g[now][j]] >= k) continue;
					q.push(g[now][j]);
				}
			}
		}
	}
	memset(ci, 0, sizeof(ci));
	for (int i = 2; i <= n; i++) {
		for (int u = 2; u <= n; u++) {
			if (u == i) continue;
			if (dis[1][u] <= k && dis[u][i] <= k)qu.push((W) {
				u
			});
		}
		while (!qu.empty() && ci[i] < 3) {
			c[i][++ci[i]] = qu.top().u;
			qu.pop();
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (dis[i][j] > k) continue;
			for (int ii = 1; ii <= ci[i]; ii++) {
				for (int jj = 1; jj <= ci[j]; jj++) {
					int u = c[i][ii], v = c[j][jj];
					if (u != j && v != i && u != v)ans = max(ans, a[u] + a[i] + a[j] + a[v]);
				}
			}
		}
	}
	cout << ans;
}