rt

考场的时候meet in middle$\Theta(n^2)$枚举点以及用双指针去合并答案（自然是挂了分的）

但是今天一试，发现双指针带一个$100$的常数+卡时就可以AC，求hack数据/kk

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#define PII pair<int,int>
#define mp make_pair
#define int long long
using namespace std;
typedef long long ll;
const int N=5e3+5;
const int M=2e4+5;
const int T=1e7+5;
const int INF=1e18;
const double MAX_TIME=1.995;
struct Edge{
	int v,w,next;
}edge[M];
struct Weight{
	int ans,u,v;
}res[T];
int n,m,k,tot=0,amt=0,ans=-INF;
int head[M],val[M],g[N][N];
inline void add(int u,int v,int w){
	edge[++tot]=(Edge){v,w,head[u]},head[u]=tot;
}
inline int read(){
	int s=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-'){f=-1;} ch=getchar();}
	while (isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
	return s*f;
}
inline void dijkstra(int s)
{
	int d[N],vis[N];
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	queue <int> q;d[s]=0;q.push(s);
	while (!q.empty())
	{
		int u=q.front();q.pop();
		if (vis[u]) continue;
		vis[u]=true;
		for (int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v,w=edge[i].w;
			if (d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				q.push(v);
			}
		}
	}
	for (int i=1;i<=n;i++)
		g[s][i]=d[i];
}
inline bool comp(Weight x,Weight y){
	return x.ans>y.ans;
}
signed main()
{
// 	freopen("holiday.in","r",stdin);
// 	freopen("holiday.out","w",stdout);
	n=read(),m=read(),k=read();
	for (int i=2;i<=n;i++) val[i]=read();
	for (int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		add(u,v,1),add(v,u,1);
	}
	for (int i=1;i<=n;i++) dijkstra(i);
	for (int i=2;i<=n;i++)
	{
		int u=i;
		if (g[1][u]>k+1) continue;
		for (int j=2;j<=n;j++)
		{
			if (j==u) continue;
			int v=j;
			if (g[u][v]>k+1) continue;
			res[++amt]=(Weight){val[u]+val[v],u,v};
		}
	}
	sort(res+1,res+1+amt,comp);
	int l=0,r=0;
	while (l<=100 && l<=amt)
	{
		l++;r=l; 
		while (r<=amt)
		{
		    if ((double)clock()/CLOCKS_PER_SEC>=MAX_TIME)
		    {
		        printf("%lld",ans);
		        return 0;
		    }
			r++;
			if (res[l].u==res[r].u || res[l].u==res[r].v) continue;
			if (res[l].v==res[r].u || res[l].v==res[r].v) continue;
    		if (res[l].v==0 || res[r].v==0) continue;
    		if (res[l].u==0 || res[r].u==0) continue;
			if (g[res[l].v][res[r].v]<=k+1)
			{
				int tmp=res[l].ans+res[r].ans;
				ans=max(ans,tmp);break;
			}
		}
	}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}