求助 55pts

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int nr = 2510;
int n, m, k, value[nr], dis[nr][nr];
vector<int> adj[nr], elig[nr];
bool cmpv(int x, int y) { return value[x] > value[y]; }

void bfs(int start)
{
    queue<int> q;
    q.push(start);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++)
        {
            if (dis[start][adj[u][i]] != 0) continue;
            dis[start][adj[u][i]] = dis[start][u] + 1;
            q.push(adj[u][i]);
        }
    }
}

signed main()
{
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) cin >> value[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) bfs(i);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            if (j != i && j != 1 && dis[1][j] <= k + 1 && dis[i][j] <= k + 1)
                elig[i].push_back(j);
        sort(elig[i].begin(), elig[i].end(), cmpv);
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++)
        {
            if (i == j) continue;
            if (dis[i][j] > k + 1) continue;
            int tans = 0;
            int size1 = elig[i].size(), size2 = elig[j].size();
            for (int k1 = 0; k1 <= min(size1 - 1, 2ll); k1++)
                for (int k2 = 0; k2 <= min(size2 - 1, 2ll); k2++)
                    if (elig[i][k1] != elig[j][k2] && elig[i][k1] != j && elig[j][k2] != i)
                        tans = max(tans, value[elig[i][k1]] + value[elig[j][k2]]);
            ans = max(ans, tans + value[i] + value[j]);
        }
    cout << ans << endl;
    return 0;
}