golang 解法, 执行用时: 232 ms, 内存消耗: 17.5 MB, 提交时间: 2023-10-10 23:06:05

func maximumScore(scores []int, edges [][]int) int {
	type nb struct{ to, s int }
	g := make([][]nb, len(scores))
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], nb{y, scores[y]})
		g[y] = append(g[y], nb{x, scores[x]})
	}
	for i, vs := range g {
		if len(vs) > 3 {
			sort.Slice(vs, func(i, j int) bool { return vs[i].s > vs[j].s })
			g[i] = vs[:3]
		}
	}

	ans := -1
	for _, e := range edges {
		x, y := e[0], e[1]
		for _, p := range g[x] {
			for _, q := range g[y] {
				if p.to != y && q.to != x && p.to != q.to {
					ans = max(ans, p.s+scores[x]+scores[y]+q.s)
				}
			}
		}
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 384 ms, 内存消耗: 137.6 MB, 提交时间: 2023-10-10 23:05:46

class Solution {
public:
    int maximumScore(vector<int> &scores, vector<vector<int>> &edges) {
        int n = scores.size();
        vector<vector<pair<int, int>>> g(n);
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].emplace_back(-scores[y], y);
            g[y].emplace_back(-scores[x], x);
        }
        for (auto &vs : g)
            if (vs.size() > 3) {
                nth_element(vs.begin(), vs.begin() + 3, vs.end());
                vs.resize(3);
            }

        int ans = -1;
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            for (auto &[score_a, a] : g[x])
                for (auto &[score_b, b] : g[y])
                    if (a != y && b != x && a != b)
                        ans = max(ans, -score_a + scores[x] + scores[y] - score_b);
        }
        return ans;
    }
};

java 解法, 执行用时: 58 ms, 内存消耗: 71.9 MB, 提交时间: 2023-10-10 23:05:34

class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        var n = scores.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(new int[]{scores[y], y});
            g[y].add(new int[]{scores[x], x});
        }
        for (var i = 0; i < n; i++)
            if (g[i].size() > 3) {
                g[i].sort((a, b) -> (b[0] - a[0]));
                g[i] = new ArrayList<>(g[i].subList(0, 3));
            }

        var ans = -1;
        for (var e : edges) {
            int x = e[0], y = e[1];
            for (var p : g[x]) {
                var a = p[1];
                for (var q : g[y]) {
                    var b = q[1];
                    if (a != y && b != x && a != b)
                        ans = Math.max(ans, p[0] + scores[x] + scores[y] + q[0]);
                }
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 564 ms, 内存消耗: 41.7 MB, 提交时间: 2023-10-10 23:05:19

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        g = [[] for _ in range(len(scores))]
        for x, y in edges:
            g[x].append((scores[y], y))
            g[y].append((scores[x], x))
        for i, vs in enumerate(g):
            if len(vs) > 3: 
                g[i] = nlargest(3, vs)

        # 下面这一段可以简写成一行，为了可读性这里就不写了
        ans = -1
        for x, y in edges:
            for score_a, a in g[x]:
                for score_b, b in g[y]:
                    if y != a != b != x:
                        ans = max(ans, score_a + scores[x] + scores[y] + score_b)
        return ans