华为非AI方向0603笔试真题-爆破小游戏(详细思路+多语言题解)

爆破小游戏华为笔试真题 6月3号 非AI方向 200分题型题目内容云小核正在玩爆破小游戏游戏提供了一张地图可以看成一棵树地图上有很多节点每个节点都有被爆破后的收益值有些节点之间有边和距离。云小核手中有一颗炸弹可以放置在任意一个节点上。这颗炸弹标定了影响范围只要和放置炸弹节点的距离路径上边的和小于等于影响范围的节点都会被爆破云小核获得的收益值是所有被爆破节点收益值的总和。请你帮云小核选择一个炸弹放置点使得云小核获得的收益最大。如下图所示当炸弹放置在节点222或节点333时获得收益最大为500500500。输入描述第111行两个整型数值NNN和KKK1≤N≤1001 \le N \le 1001≤N≤100表示节点数量1≤K≤1000000001 \le K \le 1000000001≤K≤100000000表示炸弹影响范围第222行NNN个整型数值g1,g2,…gNg_1,g_2,…g_Ng1​,g2​,…gN​0≤gi≤1000000 \le g_i \le 1000000≤gi​≤100000表示每个节点对应的收益接下来N−1N-1N−1行三个整型数值ni,nj,dkn_i,n_j,d_kni​,nj​,dk​0≤ni,nj≤N−10 \le n_i,n_j \le N-10≤ni​,nj​≤N−10≤dk≤1000000 \le d_k \le 1000000≤dk​≤100000表示节点和节点之间有条边距离为dkd_kdk​输出描述一个整型数值表示获得的最大收益样例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说明题解思路最短路算法求解根据输入的边的关系建图使用最短路算法Floyd求出不同点之间的最短距离dist,这里需要额外注意点与自身距离要设置为0.枚举爆炸点为[0, n -1]借助上一步dist累加距离小于等于k对应点价值和。其中上一步最大价值和就为结果。C#includebits/stdc.husingnamespacestd;intmain(){intn,k;cinnk;vectorintw(n);for(inti0;in;i){cinw[i];}vectorvectorintgraph(n,vectorint(n,INT_MAX));// 自身距离为0for(inti0;in;i){graph[i][i]0;}for(inti0;in-1;i){intu,v,d;cinuvd;graph[u][v]d;graph[v][u]d;}// 点和点之间距离// 初始化距离矩阵vectorvectorintdistgraph;// Floyd 求任意两点最短路for(intmid0;midn;mid){for(inti0;in;i){if(dist[i][mid]INT_MAX)continue;for(intj0;jn;j){if(dist[mid][j]INT_MAX)continue;dist[i][j]min(dist[i][j],dist[i][mid]dist[mid][j]);}}}intmaxSum0;// 枚举爆炸点for(inti0;in;i){intcurSum0;for(intj0;jn;j){if(dist[i][j]k){curSumw[j];}}maxSummax(maxSum,curSum);}coutmaxSum;return0;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intksc.nextInt();int[]wnewint[n];for(inti0;in;i){w[i]sc.nextInt();}int[][]graphnewint[n][n];for(inti0;in;i){Arrays.fill(graph[i],Integer.MAX_VALUE);}// 自身距离为0for(inti0;in;i){graph[i][i]0;}for(inti0;in-1;i){intusc.nextInt();intvsc.nextInt();intdsc.nextInt();graph[u][v]d;graph[v][u]d;}// 点和点之间距离// 初始化距离矩阵int[][]distnewint[n][n];for(inti0;in;i){System.arraycopy(graph[i],0,dist[i],0,n);}// Floyd 求任意两点最短路for(intmid0;midn;mid){for(inti0;in;i){if(dist[i][mid]Integer.MAX_VALUE){continue;}for(intj0;jn;j){if(dist[mid][j]Integer.MAX_VALUE){continue;}dist[i][j]Math.min(dist[i][j],dist[i][mid]dist[mid][j]);}}}intmaxSum0;// 枚举爆炸点for(inti0;in;i){intcurSum0;for(intj0;jn;j){if(dist[i][j]k){curSumw[j];}}maxSumMath.max(maxSum,curSum);}System.out.print(maxSum);}}pythonn,kmap(int,input().split())wlist(map(int,input().split()))INFfloat(inf)graph[[INF]*nfor_inrange(n)]# 自身距离为0foriinrange(n):graph[i][i]0for_inrange(n-1):u,v,dmap(int,input().split())graph[u][v]d graph[v][u]d# 点和点之间距离# 初始化距离矩阵dist[row[:]forrowingraph]# Floyd 求任意两点最短路formidinrange(n):foriinrange(n):ifdist[i][mid]INF:continueforjinrange(n):ifdist[mid][j]INF:continuedist[i][j]min(dist[i][j],dist[i][mid]dist[mid][j])max_sum0# 枚举爆炸点foriinrange(n):cur_sum0forjinrange(n):ifdist[i][j]k:cur_sumw[j]max_summax(max_sum,cur_sum)print(max_sum)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line);});rl.on(close,(){letidx0;const[n,k]lines[idx].split( ).map(Number);constwlines[idx].split( ).map(Number);constINFNumber.MAX_SAFE_INTEGER;constgraphArray.from({length:n},()Array(n).fill(INF));// 自身距离为0for(leti0;in;i){graph[i][i]0;}for(leti0;in-1;i){const[u,v,d]lines[idx].split( ).map(Number);graph[u][v]d;graph[v][u]d;}// 点和点之间距离// 初始化距离矩阵constdistgraph.map(row[...row]);// Floyd 求任意两点最短路for(letmid0;midn;mid){for(leti0;in;i){if(dist[i][mid]INF){continue;}for(letj0;jn;j){if(dist[mid][j]INF){continue;}dist[i][j]Math.min(dist[i][j],dist[i][mid]dist[mid][j]);}}}letmaxSum0;// 枚举爆炸点for(leti0;in;i){letcurSum0;for(letj0;jn;j){if(dist[i][j]k){curSumw[j];}}maxSumMath.max(maxSum,curSum);}console.log(maxSum);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varn,kintfmt.Fscan(in,n,k)w:make([]int,n)fori:0;in;i{fmt.Fscan(in,w[i])}constINF0x3f3f3f3fgraph:make([][]int,n)fori:0;in;i{graph[i]make([]int,n)forj:0;jn;j{graph[i][j]INF}}// 自身距离为0fori:0;in;i{graph[i][i]0}fori:0;in-1;i{varu,v,dintfmt.Fscan(in,u,v,d)graph[u][v]d graph[v][u]d}// 点和点之间距离// 初始化距离矩阵dist:make([][]int,n)fori:0;in;i{dist[i]make([]int,n)copy(dist[i],graph[i])}// Floyd 求任意两点最短路formid:0;midn;mid{fori:0;in;i{ifdist[i][mid]INF{continue}forj:0;jn;j{ifdist[mid][j]INF{continue}ifdist[i][mid]dist[mid][j]dist[i][j]{dist[i][j]dist[i][mid]dist[mid][j]}}}}maxSum:0// 枚举爆炸点fori:0;in;i{curSum:0forj:0;jn;j{ifdist[i][j]k{curSumw[j]}}ifcurSummaxSum{maxSumcurSum}}fmt.Print(maxSum)}