WA on #9#10#15

思路：将所有 $1$ 可达的点选出权值前 $4$ 大的，$\text{O}(n\log n+16n^2)$ 的时间复杂度。

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

#define ll long long

const int N = 2510, M = 20010, K = 110;
int n, m, k;
ll a[N], ans;
int hd[N], ed[M], nt[M], cnt;
int dis[N][N];
int q[N], l, r;
bool vis[N];
vector<int> v;

void add_edge (int u, int v)
{
    ed[++cnt] = v;
    nt[cnt] = hd[u];
    hd[u] = cnt;
}

void bfs (int s)
{
    memset (vis, 0, sizeof vis);
    l = r = 0;
    q[++r] = s;
    dis[s][s] = 0;
    while (l < r)
    {
        int u = q[++l];
        for (int i = hd[u]; i; i = nt[i])
        {
            int v = ed[i];
            if (!vis[v])
            {
                dis[s][v] = dis[s][u] + 1;
                vis[v] = 1;
                q[++r] = v;
            }
        }
    }
}

int main()
{
    scanf ("%d%d%d", &n, &m, &k);
    k++;
    for (int i = 2; i <= n; i++)
        scanf ("%lld", &a[i]);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf ("%d%d", &u, &v);
        add_edge (u, v);
        add_edge (v, u);
    }
    memset (dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; i++)
        bfs (i);
    for (int i = 2; i <= n; i++)
    {
        if (dis[1][i] <= k)
            v.push_back (i);
    }
    sort (v.begin(), v.end(), [](int i, int j){return a[i] > a[j];});
    int sj = min (4, (int)v.size());
    for (int B = 2; B <= n; B++)
    {
        for (int C = 2; C <= n; C++)
        {
            if (B == C || dis[B][C] > k)
                continue;
            for (int i = 0; i < sj; i++)
            {
                for (int j = 0; j < sj; j++)
                {
                    if (v[i] == v[j] || v[i] == B || v[i] == C || v[j] == B || v[j] == C || dis[v[i]][B] > k || dis[C][v[j]] > k)
                        continue;
                    ans = max (ans, a[B] + a[C] + a[v[i]] + a[v[j]]);
                }
            }
        }
    }
    printf ("%lld\n", ans);
    return 0;
}