提交记录

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MAXN = 2505;
int n, m, k;
LL A[MAXN], f[4][MAXN];
vector<int> Adjb[MAXN], Adjf[MAXN];
int vis[MAXN][MAXN];
int fn[4][MAXN];

void bfs(int u) {
	queue<pair<int, int> > q;
	q.push(make_pair(u, -1));
	while(!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop();
		//0cout << x << "->" << y << endl;
		if(y >= k) break;
		int sz = Adjb[x].size();
		for(int i = 0; i < sz; i++) {
			int v = Adjb[x][i];
			//cout << "--==-- " << vis[u][v] << endl;
			//cout << "-|-" << v << endl;
			if(vis[u][v] == 0) {
 				vis[u][v] = 1;
				//Adjf[u].push_back(v);
				//cout << "-|" << v << endl;
				q.push(make_pair(v, y + 1));
			}
		}
	} 
	return;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 2; i <= n; i++) scanf("%lld", &A[i]);
	for(int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		Adjb[u].push_back(v);
		Adjb[v].push_back(u);
	}
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i++) 
		bfs(i);
	for(int i = 1; i <= n; i++) vis[i][i] = 0;
	/*
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++)
			cout << vis[i][j] << " ";
		cout << endl;
	} 
	*/
	for(int v = 2; v <= n; v++) {
		for(int mid = 2; mid <= n; mid++) {
			if(mid != v && vis[1][mid] && vis[mid][v]) {
				if(A[mid] > f[1][v]) {
					f[3][v] = f[2][v];
					fn[3][v] = fn[2][v];
					f[2][v] = f[1][v];
					fn[2][v] = fn[1][v];
					f[1][v] = A[mid];
					fn[1][v] = mid;
				} else if(A[mid] > f[2][v]) {
					f[3][v] = f[2][v];
					fn[3][v] = fn[2][v];
					f[2][v] = A[mid];
					fn[2][v] = mid;	
				} else if(A[mid] > f[3][v]) {
					f[3][v] = A[mid];
					fn[3][v] = mid;
				}
			}
		}
	}
	LL ans = -1;
	for(int i = 2; i <= n; i++) {
		for(int j = 2; j <= n; j++) {
			if(i != j && vis[i][j] && f[1][i] && f[1][j]) {
				LL juans = 0;
				for(int a = 1; a <= 3; a++) 
					for(int b = 1; b <= 3; b++)
						if(fn[a][i] != 0 && fn[b][j] != 0 && fn[a][i] != fn[b][j] && fn[a][i] != j && fn[b][j] != i) 
							juans = max(juans, f[a][i] + f[b][j]);
				ans = max(ans, juans + A[i] + A[j]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}