求调

65pts代码

#include<bits/stdc++.h>
using namespace std;
const int N=2500;
int n,m,k,z[N+10],y[N+10][N+10];
vector<int> a[N+10];
void bfs(int p){
	queue<int> q;
	q.push(p);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		if(y[p][t]==k){continue;}
		for(int i=0;i<a[t].size();i++){
			if(y[p][a[t][i]]==-1){
				y[p][a[t][i]]=y[p][t]+1;
				q.push(a[t][i]);
			}
		}
	}
	y[p][p]=-1;
}
inline bool gmx(int &a, int b) {
	return b>a?a=b,true:false;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++){
		scanf("%d",&z[i]);
	}
	int x,y1;
	for(int i=1;i<=m;i++){
		cin >> x >> y1;
		a[x].push_back(y1),a[y1].push_back(x);
	}
	memset(y,-1,sizeof(y));
	bfs(1);
	int g[N][3]={0};
	for(int i=2;i<=n;i++){
		bfs(i);
		int &x1=g[i][0],&x2=g[i][1],&x3=g[i][2];
		for(int j=2;j<=n;j++){
			if(y[i][j]!=-1){
				if(z[j]>z[x1]){
					x3=x2,x2=x1,x1=j;
					continue;
				}
				if(z[j]>z[x2]){
					x3=x2,x2=j;
					continue;
				}
				if(z[j]>z[x3]){
					x3=j;
				}
			}
		}
	}
	int ans=0;
	for(int b=2;b<=n;b++){
		for(int c=2;c<=n;c++){
			if(y[b][c]!=-1){
				for(int i=0;i<3;i++){
					int a=g[b][i];
					for(int j=0;j<3;j++){
						int d=g[c][j];
						if(a!=c&&a!=d&&b!=d&&y[1][a]!=-1&&y[1][d]!=-1){
							gmx(ans,z[a]+z[b]+z[c]+z[d]);
						}
					}
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}