萌新求助 85pts

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
struct EDGE{
	int v,last;
}Edge[20005];
ull ans;
int ecnt;
int n,m,k;
ll f[2505];
ll g[2505];
ll s[2505];
int p[2505];
int maxp[2505][5];
int dis[2505][2505];
priority_queue<pi,vector<pi>,greater<pi> > pq;
template<typename T>
inline void input(T &x){
	x=0;char c=getchar();
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	int p=1;if (c=='-') {p=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();x*=p;
}
void write(ull x){
	if (x<10){
		putchar((char)(x+'0'));return;
	}
	write(x/10);
	putchar((char)(x%10+'0'));
}
inline void output(ull x,char c){
	write(x);putchar(c);
}
inline ull max(ull a,ull b){
	return a>b?a:b;
}
inline void doit(int st){
	memset(dis[st],0x3f,sizeof(dis[st]));
	dis[st][st]=0;pq.push(make_pair(0,st));
	while(!pq.empty()){
		pi now=pq.top();pq.pop();
		int d=now.first;
		int u=now.second;
		if (d>dis[st][u]) continue;
		for (int i=p[u];i!=-1;i=Edge[i].last){
			int v=Edge[i].v;
			if (d+1<dis[st][v]){
				dis[st][v]=d+1;
				pq.push(make_pair(dis[st][v],v));
			}
		}
	}
}
inline void init(){
	ecnt=0;memset(p,-1,sizeof(p));
}
inline void insert(int u,int v){
	Edge[++ecnt].v=v;
	Edge[ecnt].last=p[u];
	p[u]=ecnt;
}
int main(){
	freopen("holiday.in","r",stdin);
	freopen("holiday.out","w",stdout);
	input(n);input(m);input(k);
	for (int i=2;i<=n;i++){
		input(s[i]);
	}
	init();
	for (int i=0;i<m;i++){
		int u,v;
		input(u);input(v);
		insert(u,v);insert(v,u);
	}
	for (int i=1;i<=n;i++) doit(i);
	for (int u=1;u<=n;u++){
		for (int v=2;v<=n;v++){
			if (v==u) continue;
			if (dis[1][v]<=k+1&&dis[v][u]<=k+1){
				if (s[v]>s[maxp[u][1]]){
					maxp[u][3]=maxp[u][2];
					maxp[u][2]=maxp[u][1];
					maxp[u][1]=v;
				}
				else if (s[v]>s[maxp[u][2]]){
					maxp[u][3]=maxp[u][2];
					maxp[u][2]=v;
				}
				else if (s[v]>s[maxp[u][3]]){
					maxp[u][3]=v;
				}
			}
		}
	}
	for (int b=2;b<=n;b++){
		if (!maxp[b][1]) continue;
		for (int c=2;c<=n;c++){
			if (!maxp[c][1]) continue;
			if (b==c) continue;
			if (dis[b][c]<=k+1){
				ull now=0;
				for (int j=1;j<4;j++){
					for (int k=1;k<4;k++){
						if (maxp[b][j]!=maxp[c][k]&&maxp[b][j]!=c&&maxp[c][k]!=b){
							now=max(now,s[maxp[b][j]]+s[b]+s[c]+s[maxp[c][k]]);
						}
					}
				}
				ans=max(ans,now);
			}
		}
	}
	output(ans,'\n');
	return 0;
}