借鉴的第一篇题解的思路

#include<bits/stdc++.h>

using namespace std;

int n,m,k;
long long ans;
long long w[2505];
int g[2505][2505],mp[2505][2505];
//g[i][j]=f[j][i]=1表示点i,j之间有直达线路,其实就是存一下图 
//mp[i][j]=1表示通过BFS确定k次转车后i能到j点，=0则不能 
int f[2505][3];//f[u][k]表示u可达，且在家附近的，权值第k大的景点
//f[i][0]是最优,f[i][1]是次优,f[i][2]是次次优 

void bfs(int x){//通过BFS确定从x点能到哪些点(u)，能到的mp[x][u]=1 
	int dis[2505]={0};
	queue<int> q;
	q.push(x);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u!=x){
			mp[x][u]=1;
		}
		if(dis[u]==k+1) continue;
		for(int i=1;i<=n;i++){
			if(g[u][i] && dis[i]==0 && i!=x){
				q.push(i);
				dis[i]=dis[u]+1;
			}
		}
	}
}

bool cmp(int a,int b){
	return w[a]>w[b];
}

int main(){
	//板块1：输入存图 
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++){
		scanf("%lld",&w[i]);
	}
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		g[x][y]=mp[x][y]=g[y][x]=mp[y][x]=1;
	}
	//板块二：处理图，判断i(不)借助转车能到哪些点 
	for(int i=1;i<=n;i++){
		bfs(i);
	}
	//板块三：循环得b,c可达，且在家附近的，权值最大/次大/次次大的点 
	for(int i=2;i<=n;i++){
		int s=0;
		for(int j=2;j<=n;j++){
			if(mp[i][j] && mp[j][1]){
				if(s!=3){
					f[i][s++]=j;
					sort(f[i],f[i]+3,cmp);
				}else{
					if(w[j]>w[f[i][2]]){
						f[i][2]=j;
						sort(f[i],f[i]+3,cmp);
					}
				}
			}
		}
	}
	//板块四：循环b,c所有情况，列举f[b][i],f[c][j]所有情况，求最优解 
	for(int b=2;b<=n;b++){
		for(int c=2;c<=n;c++){	
			if(mp[b][c]){
				for(int i=0;i<3;i++){
					for(int j=0;j<3;j++){
						if(f[b][i]!=0 && f[c][j]!=0){
							int a=f[b][i],d=f[c][j];
							if(a!=d && a!=c && b!=d){
								ans=max(ans,w[a]+w[b]+w[c]+w[d]);
							}
						}
					}
				}
			}
		}
	}

	printf("%lld",ans);
	
	return 0;
}