#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;
}
标签:int,LL,d%,top3,long,T1,2022,include,CSP
From: https://www.cnblogs.com/ronchen/p/17723103.html