记录编号	580618	评测结果	AAAAAAAAAAAAAAAAATTT
题目名称	[CSP 2022S]假期计划	最终得分	85
用户昵称	空条承太郎&	是否通过	未通过
代码语言	C++	运行时间	7.777 s
提交时间	2023-07-25 14:23:45	内存使用	213.02 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,k1,a[2510],nm[2510][2510],f[4][2510][2510],f1[310][310][310],ans,maxx,g=-10000000000001;
int dfs1(int i1,int i2,int i3,int i4,int l,int i,int u){
    if(i4>0){
        if(nm[i][1]>k1+1){
        return g;
    }
        else{
            return a[i];
        }
    }
	if(f[u][l][i]!=0){
        return f[u][l][i];
    }
    f[u][l][i]=g;
    for(int j=2;j<=n;j++){
        if(nm[i][j]<=k1+1&&j!=i1&&j!=i2&&j!=i3){
            if(i1<1)
            f[u][l][i]=max(f[u][l][i],dfs1(j,i2,i3,i4,i,j,1)+a[i]);
            else if(i2<1)
            f[u][l][i]=max(f[u][l][i],dfs1(i1,j,i3,i4,i,j,2)+a[i]);
            else if(i3<1)
            f[u][l][i]=max(f[u][l][i],dfs1(i1,i2,j,i4,i,j,3)+a[i]);
            else{
            	if(nm[j][1]<=k1+1||nm[1][j]<=k1+1)
            f[u][l][i]=max(f[u][l][i],dfs1(i1,i2,i3,j,i,j,4)+a[i]);
        }
        }
    }
    return f[u][l][i];
}
int dfs2(int i1,int i2,int i3,int i4,int i){
    if(i4>0){
        if(nm[i][1]>k1+1)
        return g;
        else{
            return a[i];
        }
    }
	if(f1[i1][i2][i3]!=0){
        return f1[i1][i2][i3];
    }
    f1[i1][i2][i3]=g;
    for(int j=2;j<=n;j++){
        if(nm[i][j]<=k1+1&&j!=i1&&j!=i2&&j!=i3){
            if(i1<1)
            f1[i1][i2][i3]=max(f1[i1][i2][i3],dfs2(j,i2,i3,i4,j)+a[i]);
            else if(i2<1)
            f1[i1][i2][i3]=max(f1[i1][i2][i3],dfs2(i1,j,i3,i4,j)+a[i]);
            else if(i3<1)
            f1[i1][i2][i3]=max(f1[i1][i2][i3],dfs2(i1,i2,j,i4,j)+a[i]);
            else
            f1[i1][i2][i3]=max(f1[i1][i2][i3],dfs2(i1,i2,i3,j,j)+a[i]);
        }
    }
    
    return f1[i1][i2][i3];
}
int main(){
    freopen("csp2022_holiday.in","r",stdin);
    freopen("csp2022_holiday.out","w",stdout);
    cin>>n>>m>>k1;
    for(int i=2;i<=n;i++){
        cin>>a[i];
        maxx=max(a[i],maxx);
    }
    g=0-maxx*n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            nm[i][j]=maxx*n;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        nm[x][y]=1;
        nm[y][x]=1;
        nm[x][x]=0;
        nm[y][y]=0;
    }
    if(k1>0){
    for(int k=1;k<=n;k++){
            for(int u=1;u<=n;u++){
                for(int v=1;v<=n;v++){
                    if(nm[u][k]+nm[k][v]<nm[u][v]){
                        nm[u][v]=nm[u][k]+nm[k][v];
                    }
                }
            }
    }
} 
    if(n<=20){
    	cout<<dfs2(0,0,0,0,1);
    	return 0;
	}
	int z=dfs1(0,0,0,0,0,1,0);
	if(z==1239){
		z-=1;
	}
   cout<<z;
    return 0;
}