P9327 [CCC 2023 S4] Minimum Cost Roads题目描述作为新当选的基奇纳市市长Alanna 的首要任务是改善城市的道路规划。基奇纳当前的道路规划可以表示为NNN个交叉路口和MMM条道路的集合其中第iii条道路的长度为lil_ili米每年维护费用为cic_ici美元并连接交叉路口uiu_iui和viv_ivi。为了制定计划Alanna 必须选择保留和维护的MMM条道路的一个子集该计划的费用是该子集中所有道路的维护费用之和。为了降低城市的年度支出Alanna 希望将计划的费用最小化。然而城市还要求她最小化交叉路口之间的旅行距离并拒绝任何不符合这些规则的计划。正式地对于任何交叉路口对(i,j)(i, j)(i,j)如果在现有道路规划中存在从iii到jjj的路径且路径长度为lll米则 Alanna 的计划中也必须包含一条长度不超过lll米的路径。输入格式第一行包含整数NNN和MMM。接下来的MMM行中的每一行包含整数ui,vi,liu_i, v_i, l_iui,vi,li和cic_ici表示当前存在一条从交叉路口uiu_iui到交叉路口viv_ivi的道路长度为lil_ili费用为cic_ici1≤ui,vi≤N,ui≠vi1 \leq u_i, v_i \leq N, u_i \neq v_i1≤ui,vi≤N,uivi。下表显示了可用的 15 分数的分布。分数NNN和MMM的界限lil_ili的界限cic_ici的界限额外约束333分1≤N≤20001 \leq N\leq 20001≤N≤2000,1≤M≤20001\leq M \leq 20001≤M≤2000li0l_i 0li01≤ci≤1091 \leq c_i \leq 10^91≤ci≤109无。666分1≤N≤20001 \leq N\leq 20001≤N≤2000,1≤M≤20001\leq M \leq 20001≤M≤20001≤li≤1091 \leq l_i \leq 10^91≤li≤1091≤ci≤1091 \leq c_i \leq 10^91≤ci≤109在任意一对交叉路口之间最多只有一条道路。666分1≤N≤20001 \leq N\leq 20001≤N≤2000,1≤M≤20001\leq M \leq 20001≤M≤20000≤li≤1090 \leq l_i \leq 10^90≤li≤1091≤ci≤1091 \leq c_i \leq 10^91≤ci≤109无。输出格式输出一个整数表示满足要求的道路规划的最小可能费用。输入输出样例 #1输入 #15 7 1 2 15 1 2 4 9 9 5 2 5 6 4 5 4 4 4 3 3 7 1 3 2 7 1 4 2 1输出 #125说明/提示样例输入的输出解释这是交叉路口的图示以及一个具有最小费用的有效道路规划。每条边都标有一个对(l,c)(l, c)(l,c)表示其长度为lll米费用为ccc美元。此外计划中的道路用蓝色突出显示总费用为71674257 1 6 7 4 257167425。可以证明我们无法创建一个更便宜且符合城市要求的计划。本题采用捆绑测试子任务 13 分数据保证1≤N≤20001\leq N \leq 20001≤N≤20001≤M≤20001\leq M \leq 20001≤M≤2000li0l_i 0li01≤ci≤1091\leq c_i \leq 10^91≤ci≤109。子任务 26 分数据保证1≤N≤20001\leq N\leq 20001≤N≤20001≤M≤20001\leq M \leq 20001≤M≤20001≤li≤1091\leq l_i \leq 10^91≤li≤1091≤ci≤1091\leq c_i \leq 10^91≤ci≤109且在任何一对十字路口之间最多只有一条路。子任务 36 分数据保证1≤N≤20001\leq N\leq 20001≤N≤20001≤M≤20001\leq M \leq 20001≤M≤20000≤li≤1090\leq l_i \leq 10^90≤li≤1091≤ci≤1091\leq c_i \leq 10^91≤ci≤109。题面翻译由 ChatGPT-4o 提供。C实现#includeiostream#includealgorithm#includevector#includequeue#includeutilityusingnamespacestd;constintN2005;constintinf1e95;intn,m;structnode{intu,v,l,p;booloperator(node p2){if(l!p2.l)returnlp2.l;returnpp2.p;}}a[N];vectorpairint,intg[N];intdis[N];intvis[N];priority_queuepairint,intpq;intlength(intx,inty){for(inti1;in;i)dis[i]inf,vis[i]0;dis[x]0;pq.push((pairint,int){0,x});while(!pq.empty()){intupq.top().second;pq.pop();if(vis[u])continue;intv;for(inti0;ig[u].size();i){vg[u][i].first;intwg[u][i].second;if(dis[u]wdis[v]){dis[v]dis[u]w;pq.push((pairint,int){-dis[v],v});}}}returndis[y];}intmain(){cinnm;for(inti1;im;i){cina[i].ua[i].va[i].la[i].p;}sort(a1,am1);intu,v,l,p;longlongans0;for(inti1;im;i){ua[i].u,va[i].v,la[i].l,pa[i].p;if(length(u,v)l)ansp,g[u].push_back((pairint,int){v,l}),g[v].push_back((pairint,int){u,l});}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
