rt，做法就是 $\mathcal O (\frac{nmk}{\omega})$ 算出每个点 k 步以内能达到的点，然后记录每个长度为 2 的路径的前 3 大算一下

#include <bits/stdc++.h>

using namespace std;

const int NR = 2505;
const int MR = 10005;

int U[MR], V[MR], n, m, k, pl[4][NR];
long long a[NR], sum[NR][NR], mx[4][NR], ans;
bool E[NR][NR];
bitset < NR > e[101][NR];

signed main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 2; i <= n; ++i) scanf("%lld", &a[i]);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &U[i], &V[i]);
        e[0][U[i]][V[i]] = 1, e[0][V[i]][U[i]] = 1;
    }
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j <= n; ++j) e[i + 1][j] |= e[i][j];
        for (int j = 1; j <= m; ++j) e[i + 1][V[j]] |= e[i][U[j]], e[i + 1][U[j]] |= e[i][V[j]];
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) E[i][j] = e[k][i][j];
    for (int i = 2; i <= n; ++i) 
        for (int j = 2; j <= n; ++j) { 
            if (j == i) continue;
            if (E[1][i] && E[i][j]) sum[i][j] = a[i] + a[j];
            if (sum[i][j] >= mx[1][j]) mx[3][j] = mx[2][j], pl[3][j] = pl[2][j], mx[2][j] = mx[1][j], pl[2][j] = pl[1][j], mx[1][j] = sum[i][j], pl[1][j] = i;
            else if (sum[i][j] < mx[1][j] && sum[i][j] >= mx[2][j]) mx[3][j] = mx[2][j], pl[3][j] = pl[2][j], mx[2][j] = sum[i][j], pl[2][j] = i;
            else if (sum[i][j] < mx[2][j] && sum[i][j] >= mx[3][j]) mx[3][j] = sum[i][j], pl[3][j] = i;
        }
    for (int i = 2; i <= n; ++i) 
        for (int j = 2; j <= n; ++j)
            if (i != j && E[i][j]) {
                for (int x = 1; x <= 3; ++x)
                    for (int y = 1; y <= 3; ++y) {
                        int k = pl[x][i], l = pl[y][j];
                        if (k != 0 && l != 0 && k != i && k != j && l != i && l != j && k != l) ans = max(ans, mx[x][i] + mx[y][j]);
                    }
            }
    printf("%lld\n", ans);
    return 0;
}