大致思路是二次建图

前两个样例都过了，第三个RE

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <queue>

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;

const int N = 2510,M = 30010;

int n,m,k;
int h[N],e[M],ne[M],idx;
LL w[M];
int dist[N][N];
bool vis[N];
LL scor[N];
LL ans = -(LL(1) << 60);
priority_queue<PII,vector<PII>,greater<PII> > heap;
priority_queue<PII,vector<PII>,greater<PII> > emp;
queue<int> q;

void dij(int x){
    heap = emp;
    memset(vis,0,sizeof vis);
    dist[x][x] = 0;
    heap.push({0,x});
    
    while(!heap.empty()){
        PII t = heap.top();
        heap.pop();
        int ver = t.second,dis = t.first;
        if(vis[ver]) continue;
        vis[ver] = 1;
        for(int i = h[ver];~i;i = ne[i]){
            int j = e[i];
            if(dist[x][j] > dist[x][ver] + w[i]){
                dist[x][j] = dist[x][ver] + w[i];
                heap.push({dist[x][j],j});
            }
        }
        
    }
    
}

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u,int dep,LL val){
    if(dep == 5){
        if(u == n + 1) ans = max(ans,val);
        return;
    }
    
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!vis[j]){
            vis[j] = 1;
            dfs(j,dep + 1,val + w[i]);
            vis[j] = 0;
        }
    }
}


int main(){
	//freopen("r","holiday1.in",stdin);
	
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    cin >> n >> m >> k;
    
    scor[1] = 0;
    for(int i = 2;i <= n;i ++){
        cin >> scor[i];
    }
    
    for(int i = 1;i <= m;i ++){
        int x,y;
        cin >> x >> y;
        add(x,y,1);
        add(y,x,1);
    }
    
    for(int i = 1;i <= n;i ++){
        dij(i);
    }
    /*
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    */
    memset(h,-1,sizeof h);
    memset(e,0,sizeof e);
    memset(ne,0,sizeof ne);
    memset(w,0,sizeof w);
    memset(vis,0,sizeof vis);
    idx = 0;
    
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            if(i == j) continue;
            if(dist[i][j] <= k + 1){
                //cout << i << " " << j << endl;
                add(i,j,scor[j]);
                //add(j,i,scor[i]);
            }
        }
    }
    
    for(int i = h[1];~i;i = ne[i]){
        int j = e[i];
        add(j,n + 1,0);
    }
    
    dfs(1,0,0);
    
    cout << ans;
}