算了是O(nm)的复杂度，但是死活要T掉#46

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define int long long
#define maxn 2500

struct code {
    int t, w;
} p, Q[maxn << 1];
int l, r;
struct point {
    int w, v;
    point() { w = 0; }
} q[maxn + 10][4];
std :: vector <int> to[maxn + 10];
int n, m, k, x, y, ans, ll, vis[maxn + 10], v[maxn + 10], can[maxn + 10][maxn + 10];
signed main(void) {
    scanf("%lld %lld %lld", &n, &m, &k);
    for (int i = 2; i <= n; i++)
        scanf("%lld", v + i);
    while (m--) {
        scanf("%lld %lld", &x, &y);
        to[x].push_back(y), to[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        l = r = 1;
        for (int j = 1; j <= n; j++) vis[j] = 0;
        vis[i] = 1;
        for (int j = 0, maxj = to[i].size(); j < maxj; j++)
            Q[r].t = 0, Q[r].w = to[i][j], r++;
        while (l < r) {
            p = Q[l++];
            vis[p.w] = 1;
            if (p.t == k) continue;
            for (int j = 0, maxj = to[p.w].size(); j < maxj; j++)
                if (!vis[to[p.w][j]])
                    Q[r].t = p.t + 1, Q[r].w = to[p.w][j], r++;
        }
        for (int j = 1; j <= n; j++)
            if (j != i && vis[j]) can[i][j] = 1;
    }
    //for (int i = 1; i <= n; i++, putchar('\n'))
    //    for (int j = 1; j <= n; j++)
    //        printf("%lld ", can[i][j]);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (!can[1][j] || !can[i][j]) continue;
            if (!q[i][1].w || v[j] > q[i][1].v) q[i][3] = q[i][2], q[i][2] = q[i][1], q[i][1].w = j, q[i][1].v = v[j];
            else if (!q[i][2].w || v[j] > q[i][2].v) q[i][3] = q[i][2], q[i][2].w = j, q[i][2].v = v[j];
            else if (!q[i][3].w || v[j] > q[i][3].v) q[i][3].w = j, q[i][3].v = v[j];
        }
    for (int i = 2; i < n; i++)
        for (int j = i + 1; j <= n; j++) 
            for (int k = 1; k < 4; k++)
                for (int h = 1; h < 4; h++)
                    if (can[i][j] && q[i][k].w && q[j][h].w && q[i][k].w != j && q[j][h].w != i && q[i][k].w != q[j][h].w) 
                        ans = std :: max(ans, v[i] + v[j] + q[i][k].v + q[j][h].v);
    printf("%lld\n", ans);
    return 0;
}