RT，思路是先求解 $k$ 步内可达性再枚举 $(b,c)$ ，预先处理 $(1,a,b)$ 和 $(1,d,c)$ 的最大值，次大值，次次大值。

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;
using LL = long long;
using PII = pair<LL, int>;

const int N = 2510, M = 20010;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m, k;
int h[N], ver[M], ne[M], tot = 1;
LL w[N];
PII maxw[N][3];
int q[N];
int cnt[N][N];

void add(int u, int v) {
    ver[++tot] = v, ne[tot] = h[u], h[u] = tot;
}

void bfs(int S) {
    int hh = 0, tt = 1;
    q[0] = S;
    memset(cnt[S], 0x3f, sizeof cnt[S]);
    cnt[S][S] = -1;
    while (hh < tt) {
        int u = q[hh++];
        if (hh == N) hh = 0;
        for (int i = h[u]; i; i = ne[i]) {
            int v = ver[i];
            if (cnt[S][v] > cnt[S][u] + 1) {
                cnt[S][v] = cnt[S][u] + 1;
                if (cnt[S][v] <= k) {
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) bfs(i);
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++) 
            if (i != j && cnt[1][j] <= k && cnt[j][i] <= k) {
                LL t = w[i] + w[j];
                if (t > maxw[i][0].x) maxw[i][2] = maxw[i][1], maxw[i][1] = maxw[i][0], maxw[i][0] = {t, j};
                else if (t > maxw[i][1].x) maxw[i][2] = maxw[i][1], maxw[i][1] = {t, j};
                else if (t > maxw[i][2].x) maxw[i][2] = {t, j}; 
            }
    LL res = 0;
    int tmp[4];
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++) 
            if (i != j && cnt[i][j] <= k) 
                for (int u = 0; u < 3; u++)
                    for (int v = 0; v < 3; v++) 
                        if (maxw[i][u].y != j && maxw[i][u].y != maxw[j][v].y && maxw[j][v].y != i) {
                            if (res < maxw[i][u].x + maxw[j][v].x) 
                                res = maxw[i][u].x + maxw[j][v].x;
                        }
    cout << res << ' ';
    return 0;
}