思路：floyed+深搜

这是原代码（不加记忆化）

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long a[2505];
int f[2505][2505];
struct node{
	int to;
	int next;
}edge[20005];
int head[2505];
bool in[2505];
long long rep[2505][5];
long long dfs(int x,int t){
	long long res=a[x];
	if(t==4&&f[x][1]>k){
		return -6e18;
	}
	else if(t==4){
		return res;
	}
	long long rs=0;
	for(int i=head[x];i!=0;i=edge[i].next){
		int en=edge[i].to;
		if(!in[en]){
			in[en]=1;
			rs=max(rs,dfs(en,t+1));
			in[en]=0;
		}
	}
	return res+rs;
}
int main(){
	freopen("holiday.in","r",stdin);
	freopen("holiday.out","w",stdout);	
	scanf("%d %d %d",&n,&m,&k);
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	int xx,yy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d",&xx,&yy);
		f[xx][yy]=0;
		f[yy][xx]=0;
	}
	for(int g=1;g<=n;g++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][g]+f[g][j]+1);
			}
		}
	}
	int tmp=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]<=k){
				edge[++tmp].to=j;
				edge[tmp].next=head[i];
				head[i]=tmp;
			}
		}
	}
	cout<<dfs(1,0);
	return 0;
} 

50pts（TLE，输出是正确的）

这是加了记忆化的：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long a[2505];
int f[2505][2505];
struct node{
	int to;
	int next;
}edge[20005];
int head[2505];
bool in[2505];
long long rep[2505][6];
long long dfs(int x,int t){
	long long res=a[x];
	if(t==4&&f[x][1]>k){
		return -6e18;
	}
	else if(t==4){
		return res;
	}
	//long long rs=0;
	if(rep[x][t]){
		return rep[x][t];
	}
	//rep[x][t]+=res;
	for(int i=head[x];i!=0;i=edge[i].next){
		int en=edge[i].to;
		if(!in[en]){
			in[en]=1;
			rep[x][t]=max(rep[x][t],dfs(en,t+1));
			in[en]=0;
		}
	}
	rep[x][t]+=res;
	return rep[x][t];
}
int main(){
	//freopen("holiday.in","r",stdin);
	//freopen("holiday.out","w",stdout);	
	scanf("%d %d %d",&n,&m,&k);
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	int xx,yy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d",&xx,&yy);
		f[xx][yy]=0;
		f[yy][xx]=0;
	}
	for(int g=1;g<=n;g++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][g]+f[g][j]+1);
			}
		}
	}
	int tmp=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]<=k){
				edge[++tmp].to=j;
				edge[tmp].next=head[i];
				head[i]=tmp;
			}
		}
	}
	cout<<dfs(1,0);
	return 0;
} 

感觉没有问题，但是挂了QAQ

样例输入：

8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

样例输出：

27

结果加了记忆化后输出了：

31

0pts。。。

求大佬指点