题解A50000.假日计划

#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=2505;
int n,m,k,node,head[maxn],dis[maxn],vis[maxn];
bool fl[maxn][maxn];
ll ans,w[maxn];
vector<int> ve[maxn];
struct Edge{
	int  v,pre;
}edge[maxn*8];
void addedge(int u,int v){
	edge[++node].v=v;
	edge[node].pre=head[u];
	head[u]=node;
}
bool cmp(int a,int b){
	return w[a]>w[b];
}
void bfs(int st){
	memset(dis,-1,sizeof(dis));
	queue<int>  q;
	q.push(st);
	dis[st]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u!=st){
			fl[u][st]=fl[st][u]=1;
			if(st!=1&&fl[1][u]){
				ve[st].push_back(u);
			}
		}
		if(dis[u]==k+1)continue;
		for(int i=head[u];i;i=edge[i].pre){
			int v=edge[i].v;
			if(dis[v]==-1){
				dis[v]=dis[u]+1;
                q.push(v);
			}
		}
	}
	sort(ve[st].begin(),ve[st].end(),cmp);
	while(ve[st].size()>3)ve[st].pop_back();
}
int main(){
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	for(int i=1;i<=n;i++){
		bfs(i);
	}
	for(int b=2;b<=n;b++){
		for(int c=2;c<=n;c++){
			if(b==c||!fl[b][c])continue;
			for(const auto& a:ve[b]){
				for(const auto& d:ve[c]){
					if(a==d||a==c||b==d)continue;
					ans=max(ans,w[a]+w[b]+w[c]+w[d]);
				}
			}
		}
	}
	cout<<ans;
}