记录编号	577285	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022S]假期计划	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.234 s
提交时间	2022-10-30 12:33:43	内存使用	1.90 MiB

#include "bits/stdc++.h"

using i64 = long long;

const int N = 2510;
int n, m, k;
i64 w[N], dist[N], st[N];
std::vector<int> to[N], able[N], best[N];

void get(int x) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    std::queue<int> q;
    dist[x] = 0, st[x] = true;
    q.push(x);
    while (q.size()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int v : to[u]) {
            if (dist[u] + 1 < dist[v]) {
                dist[v] = dist[u] + 1;
                if (!st[v]) {
                    q.push(v),
                    st[v] = true;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        if (dist[i] <= k + 1 && i != x) {
            able[x].emplace_back(i);
        }
    }
}

int main() {
    freopen("csp2022_holiday.in", "r", stdin); 
    freopen("csp2022_holiday.out", "w", stdout);
    std::cin >> n >> m >> k;
    for (int i = 2; i <= n; ++ i) {
        std::cin >> w[i];
    }
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        std::cin >> x >> y;
        to[x].emplace_back(y),
        to[y].emplace_back(x);
    }
    for (int i = 1; i <= n; ++ i) {
        get(i);
    }
    std::sort(able[1].begin(), able[1].end(), [&] (i64 x, i64 y) {
        return w[x] > w[y]; 
    });
    for (int u : able[1]) {
        for (int v : able[u]) {
            if (best[v].size() < 3) {
                best[v].emplace_back(u);
            }
        }
    }
    i64 ans = 0;
    for (int b = 2; b <= n; ++ b) {
        for (int c : able[b]) 
            for (int a : best[b]) 
                for (int d : best[c]) 
                    if (a != d && a != c && b != d) {
                        ans = std::max(ans, w[a] + w[b] + w[c] + w[d]);
                    }
    }
    std::cout << ans << '\n';
    return 0;
}