评测记录

#include <bits/stdc++.h>
using namespace std;
int n,m,k,u,v;
long long g[2505],b[2505][2505],maxa[2505][3],ans; //维护前三大值以便ABCD的不相等 
bool a[2505][2505];
queue<int> q;

template<class T> void read(T &k){
	int t=1;char c;
	while (!isdigit(c)){
		if (c == '-') t=-1;
		c=getchar();
	}
	while (isdigit(c)){
		k=k*10+c-'0';
		c=getchar();
	}
	k *= t;
}

void bfs(int root){
	q.push(root);b[root][root]=0;
	while (!q.empty()){
		int r=q.front();q.pop();
		for (int i = 1;i <= n;i++){
			if (a[i][r] && b[root][i] > n){
				q.push(i);
				b[root][i]=b[root][r]+1;
			}
		}
	}
}

int main(){
	read(n);read(m);read(k);
	for (int i = 2;i <= n;i++) read(g[i]);
	while (m--){
		u=v=0;
		read(u);read(v);
		a[u][v]=1;a[v][u]=1;
	}
	memset(b,0x3f,sizeof(b));
	for (int i = 1;i <= n;i++) bfs(i);
	for (int i = 2;i <= n;i++){
		for (int j = 2;j <= n;j++){
			if (i != j && b[1][j]-1 <= k && b[j][i]-1 <= k){
				if (g[j] > g[maxa[i][0]]){maxa[i][2]=maxa[i][1];maxa[i][1]=maxa[i][0];maxa[i][0]=j;}
				else if (g[j] > g[maxa[i][1]]){maxa[i][2]=maxa[i][1];maxa[i][1]=j;}
				else if (g[j] > g[maxa[i][2]]) maxa[i][2]=j;
			}
		}
	}
	for (int i = 2;i <= n;i++){ //B
		for (int j = 2;j <= n;j++){ //C
			if (i != j && b[i][j]-1 <= k){
				for (int l = 0;l < 3;l++){ //A
					for (int r = 0;r < 3;r++){ //D
						if (maxa[i][l] && maxa[j][r] && maxa[i][l] != maxa[j][r] && maxa[i][l] != i && maxa[i][l] != j && maxa[j][r] != i && maxa[j][r] != j){ //A!=B!=C!=D
							ans=fmax(ans,g[maxa[i][l]]+g[i]+g[j]+g[maxa[j][r]]);
						}
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}