打卡信奥刷题（3522）用C++实现信奥题 P10949 四叶草魔杖-北京尧图网络

P10949 四叶草魔杖题目描述魔杖护法 Freda 融合了四件武器于是魔杖顶端缓缓地生出了一棵四叶草四片叶子幻发着淡淡的七色光。圣剑护法 rainbow 取出了一个圆盘圆盘上镶嵌着NNN颗宝石编号为0∼N−10 \sim N-10∼N−1。第iii颗宝石的能量是AiA_iAi。如果Ai0A_i 0Ai0表示这颗宝石能量过高需要把AiA_iAi的能量传给其它宝石如果Ai0A_i 0Ai0表示这颗宝石的能量过低需要从其它宝石处获取−Ai-A_i−Ai的能量。保证∑Ai0\sum A_i 0∑Ai0。只有当所有宝石的能量均相同时把四叶草魔杖插入圆盘中央才能开启超自然之界的通道。不过只有MMM对宝石之间可以互相传递能量其中第iii对宝石之间无论传递多少能量都要花费TiT_iTi的代价。探险队员们想知道最少需要花费多少代价才能使所有宝石的能量都相同输入格式第一行两个整数N,MN,MN,M。第二行NNN个整数AiA_iAi。接下来MMM行每行三个整数pi,qi,Tip_i,q_i,T_ipi,qi,Ti表示在编号为pip_ipi和qiq_iqi的宝石之间传递能量需要花费TiT_iTi的代价。数据保证每对pi,qip_i,q_ipi,qi最多出现一次。输出格式输出一个整数表示答案无解输出Impossible。输入输出样例 #1输入 #13 3 50 -20 -30 0 1 10 1 2 20 0 2 100输出 #130说明/提示2≤N≤162 \le N \le 162≤N≤16,0≤M≤N(N−1)20 \le M \le \dfrac{N(N-1)}{2}0≤M≤2N(N−1),0≤pi,qiN0 \le p_i,q_i N0≤pi,qiN,−1000≤Ai≤1000-1000 \le A_i \le 1000−1000≤Ai≤1000,0≤Ti≤10000 \le T_i \le 10000≤Ti≤1000C实现#includeiostream#includecstring#includealgorithm#defineregregisterusingnamespacestd;constintN17;intn,m,dp[1N],sum[1N],mst[1N],b[1N];structedge{intu,v,w;}e[300];intmain(){ios::sync_with_stdio(0);cinnm;regintx,y,z;for(inti0;in;i)cinsum[1i];for(inti0;im;i)cine[i].ue[i].ve[i].w;for(inti2;i1n;i)sum[i]sum[i^(i-i)]sum[i-i];memset(mst,0x3f,sizeofmst);mst[0]0;for(inti0;in;i)mst[1i]0;for(inti1;i1n;i)for(intj0;jm;j){xe[j].u;ye[j].v;ze[j].w;if(!(i(1x))||!(i(1y)))continue;mst[i]min({mst[i],mst[i^(1x)]z,mst[i^(1y)]z});}memset(dp,0x3f,sizeofdp);dp[0]0;for(reginti1;i1n;i){if(sum[i])continue;for(x0,yi;y;x,y^y-y)b[1x]y-y;for(regintj0;j1x;j){for(yj,z0;y;y^y-y)z|b[y-y];if(sum[z])continue;dp[i]min(dp[i],dp[z]mst[i^z]);}}if(dp[(1n)-1]0x3f3f3f3f)coutImpossible;elsecoutdp[(1n)-1];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

打卡信奥刷题（3522）用C++实现信奥题 P10949 四叶草魔杖

相关推荐

下周国内发布！华为 Pura X View 宽屏直板机来袭，宽屏手机时代已至？

写了10年Java，35岁我决定重头学AI，还用讲故事的方式

Genki 发布首款自主手柄 Manta：高度可定制，众筹价 189 美元！

更多资讯

假电工证案底吗最新政策解读

低压电工证考不了?学历不高别慌,南昌低压电工作业良心建议来了

甘肃电工证官网怎么查?之前考的证在外省能不能转过来

连州市考电工证过期怎么办？2026河南最新政策来了

惠州在哪可复审电工证？考前押题助你轻松过关

电工证报名网站网址多久拿证？实操考试心里没底怕挂科？老电工教你避坑

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？