1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
int n = scores.size();
vector<vector<int>> g(n, vector<int>());
for (auto &e : edges) {
g[e[0]].emplace_back(e[1]);
g[e[1]].emplace_back(e[0]);
}
int ans = -1;
for (int i = 0; i < n; ++i) {
sort(g[i].begin(), g[i].end(), [&](int x, int y) {
return scores[x] > scores[y];
});
}
for (auto &e : edges) {
int x = e[0], y = e[1];
for (int i = 0; i < 4 && i < g[x].size(); ++i) {
if (g[x][i] != y) {
for (int j = 0; j < 4 && j < g[y].size(); ++j) {
if (g[y][j] != x && g[x][i] != g[y][j]) {
ans = max(ans, scores[g[x][i]] + scores[x] + scores[y] + scores[g[y][j]]);
}
}
}
}
}
return ans;
}
};
|