记录编号	595836	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022S]假期计划	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	3.239 s
提交时间	2024-10-17 20:21:38	内存使用	27.06 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,cnt,he[200010],a[200010],vis[200010],d[2510][2510],s[2510][2510],v[2510][2510],w[2510][3],maxx;
struct node{
	long long v;
	long long nx;
}e[200010];
void add(long long x,long long y){
	e[++cnt].v=y,e[cnt].nx=he[x],he[x]=cnt;
} 
void p(long long x,long long y){
	if(a[y]>a[w[x][1]]){
		w[x][2]=w[x][1];
		w[x][3]=w[x][2];
		w[x][1]=y;
	}
	else if(a[y]>a[w[x][2]]){
		w[x][3]=w[x][2];
		w[x][2]=y;
	}
	else{
		if(a[y]>a[w[x][3]])
		w[x][3]=y;
	}
}
int main(){
	freopen("csp2022_holiday.in", "r", stdin); 
    freopen("csp2022_holiday.out", "w", stdout);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>a[i];
	}
	for(long long i=1;i<=m;i++){
		long long x,y;
		cin>>x>>y;
		s[x][y]=1;
		add(x,y);
		add(y,x);
	}
	for(long long k1=1;k1<=n;k1++){
		queue<long long> q;
		memset(vis,0,sizeof(vis));
		q.push(k1);
		vis[k1]=1;
		while(!q.empty()){
			long long x=q.front();
			q.pop();
			for(long long i=he[x];i;i=e[i].nx){
				long long y=e[i].v;
				if(k1==y)
				continue;
				
				if(vis[y]==0&&v[k1][x]<=k){s[k1][y]=1;
					vis[y]=1;
					q.push(y);
					v[k1][y]=v[k1][x]+1;

				}
			}
		}
	}
	for(long long i=2;i<=n;i++){
		for(long long j=2;j<=n;j++){
			
			if(j==i)continue;
			if((s[i][j]==1||s[j][i]==1)&&(s[1][j]==1&&s[j][1]==1)){
				p(i,j);
			}
		}
	}
	for(long long i=2;i<=n;i++){
		for(long long j=2;j<=n;j++){
			if(j==i)continue;
			for(long long uu=1;uu<=3;uu++){
				for(long long vv=1;vv<=3;vv++){
					if(s[i][j]==0)
					continue;
					if(w[i][uu]==0||w[j][vv]==0)
					continue;
					if(w[i][uu]==w[j][vv]){
						continue;
					}
					if(w[i][uu]==j||w[j][vv]==i)
					continue;
				    
					maxx=max(a[i]+a[j]+a[w[i][uu]]+a[w[j][vv]],maxx);
				}
			}
		}
	}
	cout<<maxx;
	return 0;
}