注1：繁星还是编程萌新，欢迎各位大佬指点。

注2：繁星于昨天刚考完，理论上此题原本为半对（考试时没做完），后面再修改的。

题目与程序：________

一、题目

假期计划（holiday）

【题目描述】

—-小熊的地图上有 n 个点，其中编号为 1 的是它的家、编号为 2, 3, . . . , n 的都是景点。部分点对之间有双向直达的公交线路。如果点 x 与 z1、z1 与 z2、……、zk−1 与 zk、zk 与 y 之间均有直达的线路，那么我们称 x 与 y 之间的行程可转车 k 次通达；特别地，如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。

—-很快就要放假了，小熊计划从家出发去 4 个不. 同. 的景点游玩，完成 5 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家且每段行程最多转车 k 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A → 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D → 家这段行程转车时经过的点。

—-假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不. 同. 景点的分数之和最大
【输入格式】

—-从文件 holiday.in 中读入数据。

—-第一行包含 3 个正整数 n, m, k，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

—-第二行包含 n − 1 个正整数，分别表示编号为 2, 3, . . . , n 的景点的分数。

—-接下来 m 行，每行包含两个正整数 x, y，表示点 x 和 y 之间有道路直接相连，保证 1 ≤ x, y ≤ n，且没有重边，自环。
【输出格式】

—-输出到文件 holiday.out 中。

—-输出一个正整数，表示小熊经过的 4 个不同景点的分数之和的最大值。

【数据范围】

—-对于所有数据，保证 5 ≤ n ≤ 2500, 1 ≤ m ≤ 10000, 0 ≤ k ≤ 100, 所有景点的分数1 ≤ si ≤ 1018。保证至少存在一组符合要求的行程。

二、程序

//作者:繁星(www.stars22.xyz)
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long s[2501],smax=0,cs[10001],mm;
int a[2501][10001],b[2501],c[10001][2],k0=0;
//int oa,ob,oc,od;//测试用到的数组
int main(){
	freopen("holiday.in","r",stdin);
	freopen("holiday.out","w",stdout); 
	cin>>n>>m>>k;//输入地图点数，道路数量，转车次数
	for(int i=1;i<=n-1;i++){//输入每个景点分数
		cin>>s[i+1];
	}
	for(int i=1;i<=m;i++){//输入并载入道路(无中转)
		int left,right;
		cin>>left>>right;
		b[left]++;
		b[right]++;
		a[left][b[left]]=right;
		a[right][b[right]]=left;
	}
	for(int i=1;i<=b[1];i++){//计算从起点出发路过两个景点的分数和
		for(int t=1;t<=b[a[1][i]];t++){
			if(a[a[1][i]][t]==1)continue;
			k0++;
			c[k0][1]=a[1][i];
			c[k0][2]=a[a[1][i]][t];
			cs[k0]=s[a[1][i]]+s[a[a[1][i]][t]];
		}
	}
	for(int i=1;i<=k0;i++){//比较获得最高分数
		for(int t=i+1;t<=k0;t++){
			int o=0;
			if(b[c[i][2]]<b[c[t][2]]){
				for(int j=1;j<=b[c[i][2]];j++){
			        if(a[c[i][2]][j]==c[t][2]){
					    o=1;
					    break;
				    }
			    }
			}
			else{
				for(int j=1;j<=b[c[t][2]];j++){
			        if(a[c[t][2]][j]==c[i][2]){
					    o=1;
					    break;
				    }
			    }
			}
			
			if(o==1&&c[i][1]!=c[t][1]&&c[i][2]!=c[t][1]&&c[i][1]!=c[t][2]&&c[i][2]!=c[t][2]){
				mm=cs[i]+cs[t];
				if(mm>smax){
					smax=mm;
					//以下为测试代码
					/*oa=c[i][1];
					ob=c[i][2];
					oc=c[t][1];
					od=c[t][2];*/
					//测试代码结束
				}
			}
		}
	}
	cout<<smax;
	//cout<<' '<<oa<<' '<<ob<<' '<<oc<<' '<<od;//此行为测试代码
	return 0;
}