文件详细信息

下载本文件

本文件的大小为 1998 字节。

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	bool flag=true;
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	flag||(num=-num);
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
namespace my_std{
	void chkmax(ll&a,const ll b){
		if(a<b)a=b;
	}
	void chkmin(ll&a,const ll b){
		if(a>b)a=b;
	}
};
const int maxn=2505,maxm=10005,inf=0x3f3f3f3f,p=4;
int n,m,k,head[maxn],total;
struct Edge{
	int to,next;
}e[maxm<<1];
void add(int u,int v){
	e[++total]=Edge{v,head[u]};
	head[u]=total;
}
ll val[maxn];
int dis[maxn][maxn];
int q[maxn],front,tail;
void bfs(int s,int*dis){
	memset(dis+1,63,sizeof(int)*n);
	front=1,tail=0;
	q[++tail]=s;
	dis[s]=0;
	while(front<=tail){
		int u=q[front++];
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				q[++tail]=v;
			}
		}
	}
}
int best[maxn][p];
ll ans=-1;
int main(){
	freopen("holiday.in","r",stdin);
	freopen("holiday.out","w",stdout);
	read(n),read(m),read(k);
	for(int i=2;i<=n;i++)read(val[i]);
	for(int i=1,u,v;i<=m;i++){
		read(u),read(v);
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++)bfs(i,dis[i]);
	for(int u=2;u<=n;u++)
		for(int v=2;v<=n;v++){
			if(u==v||dis[u][v]>k+1||dis[1][v]>k+1)continue;
			for(int i=0;i<p;i++)
				if(!best[u][i]||val[v]>val[best[u][i]]){
					for(int j=p-1;j>i;j--)best[u][j]=best[u][j-1];
					best[u][i]=v;
					break;
				}
		}
	for(int u=2;u<=n;u++)
		for(int v=2;v<=n;v++){
			if(u==v||dis[u][v]>k+1)continue;
			for(int i=0;i<p;i++)
				if(best[u][i])
					for(int j=0;j<p;j++)
						if(best[v][j]&&best[u][i]!=best[v][j]&&u!=best[v][j]&&v!=best[u][i])
							my_std::chkmax(ans,val[u]+val[v]+val[best[u][i]]+val[best[v][j]]);
		}
	write(ans),putchar('\n');
	return 0;
}