[CSP-S 2022 T1] 假期计划-526互联

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; 
typedef long long LL;
const int N = 2505;
vector<int> G[N];
int dis[N], top3[N][3];
bool vis[N], ok[N][N];
LL s[N];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 2; i <= n; i++) scanf("%lld", &s[i]); // 注意景点分数的数据范围
    for (int i = 0; i < m; i++) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y); G[y].push_back(x);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        while (!q.empty()) q.pop();
        for (int j = 1; j <= n; j++) {
            dis[j] = -1; vis[j] = false;
        }
        q.push(i); vis[i] = true; dis[i] = 0; 
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int to : G[cur]) {
                if (!vis[to]) {
                    vis[to] = true;
                    dis[to] = dis[cur] + 1;
                    if (dis[to] <= k + 1) {
                        q.push(to); ok[i][to] = true;
                    }
                }
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            // ok[i][i] 必定是 false，不列入讨论范围
            if (ok[1][j] && ok[i][j]) { 
                if (s[j] > s[top3[i][0]]) {
                    top3[i][2] = top3[i][1];
                    top3[i][1] = top3[i][0];
                    top3[i][0] = j;
                } else if (s[j] > s[top3[i][1]]) {
                    top3[i][2] = top3[i][1];
                    top3[i][1] = j;
                } else if (s[j] > s[top3[i][2]]) {
                    top3[i][2] = j;
                }
            }
        }
    }
    LL ans = 0;
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) {
            if (b == c || !ok[b][c]) continue;
            for (int i = 0; i < 3; i++) {
                int a = top3[b][i];
                if (a == 0) break;
                if (a == b || a == c) continue;
                for (int j = 0; j < 3; j++) {
                    int d = top3[c][j];
                    if (d == 0) break;
                    if (d == a || d == b || d == c) continue;
                    ans = max(ans, s[a] + s[b] + s[c] + s[d]);   
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}