爆破小游戏

华为笔试真题 6月3号 非AI方向 200分题型

题目内容

云小核正在玩爆破小游戏，游戏提供了一张地图，可以看成一棵树，地图上有很多节点，每个节点都有被爆破后的收益值，有些节点之间有边和距离。云小核手中有一颗炸弹，可以放置在任意一个节点上。这颗炸弹标定了影响范围，只要和放置炸弹节点的距离（路径上边的和）小于等于影响范围的节点，都会被爆破，云小核获得的收益值是所有被爆破节点收益值的总和。请你帮云小核选择一个炸弹放置点，使得云小核获得的收益最大。
如下图所示，当炸弹放置在节点$2$或节点$3$时，获得收益最大，为 $500$。

输入描述

• 第 $1$ 行：两个整型数值，$N$ 和 $K$，$1\le N\le 100$ 表示节点数量，$1\le K\le 100000000$ 表示炸弹影响范围
• 第 $2$ 行：$N$ 个整型数值，$g_1,g_2,\dots g_N$，$0\le g_i\le 100000$，表示每个节点对应的收益
• 接下来 $N-1$ 行：三个整型数值，$n_i,n_j,d_k$，$0\le n_i,n_j\le N-1$，$0\le d_k\le 100000$，表示节点和节点之间有条边，距离为 $d_k$

输出描述

一个整型数值，表示获得的最大收益

样例1

输入

7 3
10 10 10 300 10 10 300
0 1 1
0 2 1
1 3 3
1 4 1
2 5 3
2 6 1

输出

640

说明

样例2

输入

5 2
200 100 250 100 100
1 0 20
0 2 20
3 1 2
4 1 2

输出

300

说明

题解

思路

最短路算法求解

1. 根据输入的边的关系建图，使用最短路算法Floyd求出不同点之间的最短距离dist,这里需要额外注意点与自身距离要设置为0.
2. 枚举爆炸点为[0, n -1]，借助上一步dist累加距离小于等于k对应点价值和。
3. 其中上一步最大价值和就为结果。

C++

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
    // 自身距离为0
    for (int i = 0; i < n; i++) {
        graph[i][i] = 0;
    }
    for (int i = 0; i < n - 1; i++) {
        int u,v,d;
        cin >> u >> v >> d;
        graph[u][v] = d;
        graph[v][u] = d;
    }
    // 点和点之间距离
    // 初始化距离矩阵
    vector<vector<int>> dist = graph;

    // Floyd 求任意两点最短路
    for (int mid = 0; mid < n; mid++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][mid] == INT_MAX) continue;

            for (int j = 0; j < n; j++) {
                if (dist[mid][j] == INT_MAX) continue;

                dist[i][j] = min(
                    dist[i][j],
                    dist[i][mid] + dist[mid][j]
                );
            }
        }
    }
    int maxSum = 0;
    // 枚举爆炸点
    for (int i = 0; i < n; i++) {
        int curSum = 0;
        for (int j = 0; j < n; j++) {
            if (dist[i][j] <= k) {
                curSum += w[j];
            }
        }
        maxSum = max(maxSum, curSum);
    }
    
    cout << maxSum;
    return 0;
    
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }

        int[][] graph = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }

        // 自身距离为0
        for (int i = 0; i < n; i++) {
            graph[i][i] = 0;
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int d = sc.nextInt();

            graph[u][v] = d;
            graph[v][u] = d;
        }

        // 点和点之间距离
        // 初始化距离矩阵
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            System.arraycopy(graph[i], 0, dist[i], 0, n);
        }

        // Floyd 求任意两点最短路
        for (int mid = 0; mid < n; mid++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][mid] == Integer.MAX_VALUE) {
                    continue;
                }

                for (int j = 0; j < n; j++) {
                    if (dist[mid][j] == Integer.MAX_VALUE) {
                        continue;
                    }

                    dist[i][j] = Math.min(
                            dist[i][j],
                            dist[i][mid] + dist[mid][j]
                    );
                }
            }
        }

        int maxSum = 0;

        // 枚举爆炸点
        for (int i = 0; i < n; i++) {
            int curSum = 0;

            for (int j = 0; j < n; j++) {
                if (dist[i][j] <= k) {
                    curSum += w[j];
                }
            }

            maxSum = Math.max(maxSum, curSum);
        }

        System.out.print(maxSum);
    }
}

python

n, k = map(int, input().split())

w = list(map(int, input().split()))

INF = float('inf')

graph = [[INF] * n for _ in range(n)]

# 自身距离为0
for i in range(n):
    graph[i][i] = 0

for _ in range(n - 1):
    u, v, d = map(int, input().split())
    graph[u][v] = d
    graph[v][u] = d

# 点和点之间距离
# 初始化距离矩阵
dist = [row[:] for row in graph]

# Floyd 求任意两点最短路
for mid in range(n):
    for i in range(n):
        if dist[i][mid] == INF:
            continue

        for j in range(n):
            if dist[mid][j] == INF:
                continue

            dist[i][j] = min(
                dist[i][j],
                dist[i][mid] + dist[mid][j]
            )

max_sum = 0

# 枚举爆炸点
for i in range(n):
    cur_sum = 0

    for j in range(n):
        if dist[i][j] <= k:
            cur_sum += w[j]

    max_sum = max(max_sum, cur_sum)

print(max_sum)

javascript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];

rl.on('line', line => {
    lines.push(line);
});

rl.on('close', () => {
    let idx = 0;

    const [n, k] = lines[idx++].split(' ').map(Number);

    const w = lines[idx++].split(' ').map(Number);

    const INF = Number.MAX_SAFE_INTEGER;

    const graph = Array.from(
        { length: n },
        () => Array(n).fill(INF)
    );

    // 自身距离为0
    for (let i = 0; i < n; i++) {
        graph[i][i] = 0;
    }

    for (let i = 0; i < n - 1; i++) {
        const [u, v, d] = lines[idx++].split(' ').map(Number);

        graph[u][v] = d;
        graph[v][u] = d;
    }

    // 点和点之间距离
    // 初始化距离矩阵
    const dist = graph.map(row => [...row]);

    // Floyd 求任意两点最短路
    for (let mid = 0; mid < n; mid++) {
        for (let i = 0; i < n; i++) {
            if (dist[i][mid] === INF) {
                continue;
            }

            for (let j = 0; j < n; j++) {
                if (dist[mid][j] === INF) {
                    continue;
                }

                dist[i][j] = Math.min(
                    dist[i][j],
                    dist[i][mid] + dist[mid][j]
                );
            }
        }
    }

    let maxSum = 0;

    // 枚举爆炸点
    for (let i = 0; i < n; i++) {
        let curSum = 0;

        for (let j = 0; j < n; j++) {
            if (dist[i][j] <= k) {
                curSum += w[j];
            }
        }

        maxSum = Math.max(maxSum, curSum);
    }

    console.log(maxSum);
});

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n, k int
	fmt.Fscan(in, &n, &k)

	w := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &w[i])
	}

	const INF = 0x3f3f3f3f

	graph := make([][]int, n)
	for i := 0; i < n; i++ {
		graph[i] = make([]int, n)
		for j := 0; j < n; j++ {
			graph[i][j] = INF
		}
	}

	// 自身距离为0
	for i := 0; i < n; i++ {
		graph[i][i] = 0
	}

	for i := 0; i < n-1; i++ {
		var u, v, d int
		fmt.Fscan(in, &u, &v, &d)

		graph[u][v] = d
		graph[v][u] = d
	}

	// 点和点之间距离
	// 初始化距离矩阵
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		copy(dist[i], graph[i])
	}

	// Floyd 求任意两点最短路
	for mid := 0; mid < n; mid++ {
		for i := 0; i < n; i++ {
			if dist[i][mid] == INF {
				continue
			}

			for j := 0; j < n; j++ {
				if dist[mid][j] == INF {
					continue
				}

				if dist[i][mid]+dist[mid][j] < dist[i][j] {
					dist[i][j] = dist[i][mid] + dist[mid][j]
				}
			}
		}
	}

	maxSum := 0

	// 枚举爆炸点
	for i := 0; i < n; i++ {
		curSum := 0

		for j := 0; j < n; j++ {
			if dist[i][j] <= k {
				curSum += w[j]
			}
		}

		if curSum > maxSum {
			maxSum = curSum
		}
	}

	fmt.Print(maxSum)
}