题目大意给定一个无向图和一个常数ccc让你找到一个xxx把到111的距离小于等于xxx的点之间连接的边去掉求c×xc \times xc×x与剩余边权的和的最小值。题目分析既然要求距离我们先以111为源点跑一遍 Dijkstra求出距离之后给这些距离排序然后遍历每个点把xxx设为当前点到111的距离接下来就是去掉边的步骤。那么怎么去掉边呢我们先维护一个变量sum计算所有边权的总和同时开一个标记数组把到111的距离小于等于xxx的点标为true接着对于每条边假如它两个端点在标记数组中的值都是true那么就让sum的值减去这个边权。最后用c×xsumc \times x \texttt{sum}c×xsum更新答案。总时间复杂度DijkstraO((nm)log⁡n)O((nm)\log n)O((nm)logn)排序O(nlog⁡n)O(n \log n)O(nlogn)枚举并检查每条边O(m)O(m)O(m)整体O((nm)log⁡nm)O((nm)\log n m)O((nm)lognm)可以通过。AC代码#includebits/stdc.husingnamespacestd;#definefile_in(s)freopen(s.in,r,stdin);#definefile_out(s)freopen(s.out,w,stdout);#definefile(s)file_in(s)file_out(s)#definesz(x)((int)(x).size())#definepbpush_back#defineebemplace_back#definempmake_pair#definemtmake_tuple#definefifirst#definesesecondusinglllonglong;usingullunsignedlonglong;usingpiipairint,int;usingpllpairll,ll;usingplipairll,int;usingtiiitupleint,int,int;usingtliituplell,int,int;usingtllituplell,ll,int;templatetypenameT,typenameComparelessTusingheappriority_queueT,vectorT,Compare;constintINF0x3f3f3f3f;constll INFLL0x3f3f3f3f3f3f3f3fLL;constintMOD1e97;constdoubleEPS1e-8;constintN1e55;structsquare{intid;ll dis;}a[N];structedge{intto,next;ll w;}e[N2];intn,m,cnt0,head[N];ll c,sum0,ansINFLL,d[N];boolvhash[N];inlinevoidaddedge(intu,intv,ll w){e[cnt](edge){v,head[u],w};head[u]cnt;}voiddijkstra(){heappli,greaterpliQ;Q.push(mp(0,1));d[1]0;while(!Q.empty()){auto[cd,u]Q.top();Q.pop();if(cdd[u])continue;for(intihead[u];~i;ie[i].next){intve[i].to;ll we[i].w;if(d[v]d[u]w){d[v]d[u]w;Q.push(mp(d[v],v));}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(head,-1,sizeof(head));memset(d,INFLL,sizeof(d));cinnmc;for(inti1,u,v;im;i){ll w;cinuvw;sumw;//计算边权总和addedge(u,v,w);addedge(v,u,w);}dijkstra();//跑最短路for(inti1;in;i)a[i]{i,d[i]};sort(a1,an1,[](square x,square y){returnx.disy.dis;});//根据距离排序for(inti1;in;i){intua[i].id;//一定要用 a[i].id不要用成 i 了ll disa[i].dis;vhash[u]true;//标记该点for(intjhead[u];~j;je[j].next){intve[j].to;ll we[j].w;if(vhash[v])sum-w;//假如边两个端点都被标记过了就用 sum 减去边权}ansmin(ans,sumc*dis);//更新答案}coutans;return0;}