打卡信奥刷题（3666）用C++实现信奥题 P12220 [蓝桥杯 2023 国 Java B] 星球

P12220 [蓝桥杯 2023 国 Java B] 星球题目描述小明驾驶飞船对某星系发起攻击。星系中有nnn颗星球编号依次是1,2,…,n1, 2, \ldots, n1,2,…,n。第iii颗星球的坐标为(xi,yi,zi)(x_i, y_i, z_i)(xi​,yi​,zi​)且其防御强度为wiw_iwi​。小明需要规划出进攻这nnn颗星球的顺序使得其进攻所需能量最少。对于一个遍历顺序p1,p2,…,pnp_1, p_2, \ldots, p_np1​,p2​,…,pn​来说小明进攻需要的能量为E∑i2nd(pi−1,pi)×wpiE \displaystyle \sum_{i2}^{n} d(p_{i-1}, p_i) \times w_{p_i}Ei2∑n​d(pi−1​,pi​)×wpi​​其中d(pi−1,pi)d(p_{i-1}, p_i)d(pi−1​,pi​)表示pi−1,pip_{i-1}, p_ipi−1​,pi​两颗星球之间的直线距离。小明想知道进攻所需最少能量是多少。输入格式输入共n1n 1n1行。第一行为一个正整数nnn。后面nnn行每行四个整数xi,yi,zi,wix_i, y_i, z_i, w_ixi​,yi​,zi​,wi​。输出格式输出共111行一个浮点数保留两位小数。输入输出样例 #1输入 #13 4 3 3 5 2 2 3 5 3 1 1 3输出 #118.53说明/提示样例说明当进攻顺序为{1,2,3}\{1, 2, 3\}{1,2,3}时所需能量最小为55365\sqrt{5} 3\sqrt{6}55​36​。评测用例规模与约定对于20%20\%20%的数据保证n≤8n \leq 8n≤8。对于100%100\%100%的数据保证n≤18n \leq 18n≤180≤xi,yi,zi,wi≤1000 \leq x_i, y_i, z_i, w_i \leq 1000≤xi​,yi​,zi​,wi​≤100。C实现#includebits/stdc.h#definelllonglong#definelllunsignedlonglong#definedoulongdouble#defineStstring#definepipairint,intusingnamespacestd;constexprintN21;structnode{intx,y,z;}a[N];intn;intw[N];dou ans1e9;dou dp[N][1N];douget_dis(node x,node y){returnsqrt((x.x-y.x)*(x.x-y.x)(x.y-y.y)*(x.y-y.y)(x.z-y.z)*(x.z-y.z));}signedmain(){cinn;for(inti0;in;i){intx,y,z;cinxyzw[i];a[i](node){x,y,z};}for(inti0;in;i){for(intj0;j(1n);j){dp[i][j]1e9;}}for(inti0;in;i){dp[i][(1i)]0;}for(inti0;i(1n);i){for(ints0;sn;s){if(!((is)1))continue;for(intt0;tn;t){if(!((it)1)||st)continue;dp[t][i]min(dp[t][i],dp[s][i-(1t)]get_dis(a[s],a[t])*(1.00*w[t]));}}}for(inti0;in;i){ansmin(ans,dp[i][(1n)-1]);}coutfixedsetprecision(2)ansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容