我觉得这道题就是个最短路，SPFA 跑 $n$ 遍应该略大于 $O(n^2)$，模拟赛时间不够，我采用了 Floyd，然后加上一个 $O(n^4)$ 的枚举，采用分讨略微优化一点时间，感觉可以排序大幅减少枚举次数，求大神帮助剪枝，thx。

我的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool ed[10001][10001];
int zhuan[10001][10001];
long long val[2512];
bool cmp(long long a,long long b){
    return a>b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    memset(zhuan,-1,sizeof(zhuan));
    for(register int i=1;i<n;i++)cin>>val[i];
    for(register int i=0;i<m;i++){
        register int fr,to;
        cin>>fr>>to;
        ed[fr-1][to-1]=1;//数据较小，邻接矩阵存边比前向星快
        ed[to-1][fr-1]=1;
        zhuan[fr-1][to-1]=0;
        zhuan[to-1][fr-1]=0;
    }
    if(k==0){
        unsigned long long res=0;
        for(register int a=1;a<n;a++){//枚举
            for(register int b=1;b<n;b++){
                if(b==a)continue;
                for(register int c=1;c<n;c++){
                    if(c==a||c==b)continue;
                    for(register int d=1;d<n;d++){
                        if(d==a||d==b||d==c)continue;
                        if(ed[0][a]==1){
                            if(ed[a][b]==1){
                                if(ed[b][c]==1){
                                    if(ed[c][d]==1){
                                        if(ed[d][0]==1){
                                            if(val[a]+val[b]+val[c]+val[d]>res){//因为没有预处理转车，肯定转车次数为0
                                                res=val[a]+val[b]+val[c]+val[d];
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout<<res;
    }else{
        for(register int a=0;a<n;a++){//跑Floyd（Floyed）
            for(register int b=0;b<n;b++){
                if(b==a)continue;
                for(register int c=0;c<n;c++){
                    if(c==a||c==b)continue;
                    if(ed[a][b]&&ed[b][c]){
                        ed[a][c]=1;
                        if(zhuan[a][c]==-1||zhuan[a][b]+zhuan[b][c]+1<zhuan[a][c])zhuan[a][c]=zhuan[a][b]+zhuan[b][c]+1;//计算转车次数
                    }
                }
            }
        }
        unsigned long long res=0;
        for(register int a=1;a<n;a++){//枚举
            for(register int b=1;b<n;b++){
                if(b==a)continue;
                for(register int c=1;c<n;c++){
                    if(c==a||c==b)continue;
                    for(register int d=1;d<n;d++){
                        if(d==a||d==b||d==c)continue;
                        if(ed[0][a]==1){
                            if(ed[a][b]==1){
                                if(ed[b][c]==1){
                                    if(ed[c][d]==1){
                                        if(ed[d][0]==1){
                                            if(zhuan[0][a]>k||zhuan[a][b]>k||zhuan[b][c]>k||zhuan[c][d]>k||zhuan[d][0]>k)continue;//转车不能多于k次
                                            if(val[a]+val[b]+val[c]+val[d]>res){
                                                res=val[a]+val[b]+val[c]+val[d];
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout<<res;
    }
}

我觉得优化下可以比 $45$ 分多，感激不尽！