首页/新闻资讯/正文详情

UVa 685 Least Path Cost

发布时间:2026/11/23 4:24:17 来源:云帆数科 栏目:资讯中心
UVa 685 Least Path Cost
题目描述给定一个平面图由M MM条线段组成每条线段有高度正整数线段仅在端点相交且不重叠。每条线段由两个端点编号1 11到N NN表示。一条路径定义为线段的序列L C 1 , L C 2 , … , L C k L_{C_1}, L_{C_2}, \ldots, L_{C_k}LC1​​,LC2​​,…,LCk​​满足k 1 k 1k1且C i ≠ C j C_i \neq C_jCi​Cj​线段不重复相邻线段共享一个端点起点线段的某一端点是孤立端点不与其他线段相交终点线段的某一端点也是孤立端点。路径成本为k ⋅ Δ ∑ i 1 k − 1 ∣ height ( L C i ) − height ( L C i 1 ) ∣ k \cdot \Delta \sum_{i1}^{k-1} |\text{height}(L_{C_i}) - \text{height}(L_{C_{i1}})|k⋅Δi1∑k−1​∣height(LCi​​)−height(LCi1​​)∣其中Δ \DeltaΔ是给定开销。求所有路径中的最小成本。输入格式第一行为测试用例数l ll。每个测试用例第一行为三个整数M MM、N NN、Δ \DeltaΔ。接下来M MM行每行三个整数表示一条线段的两端点编号及其高度。输出格式对于每个测试用例输出一行即最小路径成本。样例输入2 8 9 25 1 2 1 8 9 10 7 8 9 1 4 2 4 5 20 1 3 9 3 5 9 5 6 8 6 21 1 2 1 1 4 2 4 5 20 1 3 9 3 5 9 5 6 8输出51 93题目分析本题可建模为图论问题。每条线段是一个节点相邻线段共享端点之间连边边权为高度差绝对值加上Δ \DeltaΔ但Δ \DeltaΔ是在路径总成本中按线段个数乘以Δ \DeltaΔ而非每条边加Δ \DeltaΔ。路径起点和终点必须是孤立端点所在的线段。我们需要找到从任意起点线段到任意终点线段的最短路径其中路径长度k kk的计算方式特殊总成本为k ⋅ Δ ∑ k \cdot \Delta \sumk⋅Δ∑高度差。一种方法是将每个端点作为图中的节点线段作为边但路径成本涉及线段的个数。我们可以将问题转化为在“线段图”上的最短路径其中节点为线段边权为高度差绝对值另外每走一条边进入一个新线段增加Δ \DeltaΔ但起点线段本身也计1 11个Δ \DeltaΔ。因此我们可以对每条线段计算从起点到该线段的最小成本状态为(线段, 是否已访问过)但由于线段不重复直接DFS \texttt{DFS}DFS枚举所有路径即可M ≤ 200 M \le 200M≤200N ≤ 400 N \le 400N≤400。解题思路建立端点与线段的关联对于每个端点存储所有与该端点相连的线段即线段端点。对每个可能的起点线段即该线段有一个端点只属于它自己即度为1 11的端点执行深度优先搜索DFS \texttt{DFS}DFS当前线段i当前路径长度length线段数上一条线段高度previous当前总成本cost。若当前线段有一个端点度为1 11且length 2则更新最小成本。否则遍历与当前线段共享端点的其他线段若未访问过则递归。剪枝若当前成本已超过已知最优解则提前返回。输出最小成本。复杂度分析每个状态为 (线段, 访问位掩码) 的组合但M ≤ 200 M \le 200M≤200DFS \texttt{DFS}DFS可能枚举所有路径但通过剪枝和路径数量有限可接受。代码实现// Least Path Cost// UVa ID: 685// Verdict: Accepted// Submission Date: 2017-06-10// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{intstart,end,height;};intM,N,D;vectorvectoredgeedges(410,vectoredge());vectorintvisited(410);intminCost-1;voiddfs(inti,intlength,intprevious,intcost){if(minCost!-1length2costminCost)return;if(previous!-1length2edges[i].size()1){if(minCost-1)minCostcost;elseminCostmin(minCost,cost);}else{for(autoe:edges[i]){if(visited[e.end])continue;visited[i]1;if(previous-1)dfs(e.end,length1,e.height,costD);elsedfs(e.end,length1,e.height,costDabs(e.height-previous));visited[i]0;}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;intstart,end,height;cincases;for(intc1;ccases;c){cinMND;for(inti1;iN;i)edges[i].clear();for(inti1;iM;i){cinstartendheight;edges[start].push_back(edge{start,end,height});edges[end].push_back(edge{end,start,height});}minCost-1;for(inti1;iN;i){if(edges[i].size()!1)continue;fill(visited.begin(),visited.end(),0);dfs(i,0,-1,0);}coutminCost\n;}return0;}总结本题通过将线段视为图节点利用深度优先搜索枚举所有可能的路径并剪枝优化求解最小路径成本。关键点包括正确建模路径的起点和终点度为1 11的端点。路径成本包括线段个数乘以Δ \DeltaΔ和高度差之和。使用DFS \texttt{DFS}DFS枚举所有简单路径线段不重复并剪枝。该解法适用于M ≤ 200 M \le 200M≤200的中等规模图。

相关推荐

KVM虚拟化技术实战:从安装配置到性能优化
KVM虚拟化技术实战:从安装配置到性能优化

1. KVM虚拟化技术概述KVM(Kernel-based Virtual Machine)作为Linux内核原生支持的虚拟化解决方案,已经成为企业级虚拟化部署的首选方案之一。与传统的Type-2虚拟化方案不同,KVM直接利用Linux内核作为hypervisor,通过内… · 2026/9/20 18:31:08

MRAM内存芯片是什么,MRAM内存芯片存储原理
MRAM内存芯片是什么,MRAM内存芯片存储原理

一、MRAM内存芯片是什么 MRAM内存芯片全称磁随机存取存储器,是半导体存储领域新一代热门的非易失性存储芯片,依托磁电阻效应实现数据存储,彻底打破了传统存储芯片的性能局限。不同于常规存储器件,该芯片主要依靠磁场极化方式记录数… · 2026/11/22 10:00:02

什么是产品经理?
什么是产品经理?

为什么需要产品经理?直接给答案:因为组织的分工,会导致没有人对全局的投入产出比负责。我们看一个没有产品经理的团队,各个角色都在追求什么:设计师:追求极致的用户体验。一个按钮的位置、一个动画的流畅度… · 2026/11/15 0:23:43

南阳电工证换证别踩坑,含金量还在吗?
南阳电工证换证别踩坑,含金量还在吗?

南阳电工证换证别踩坑,含金量还在吗? 证书过期了不知道怎么复审延期?南阳电工证换证流程复杂又绕,很多人一不小心就错过了有效期,结果证书失效,工作机会也被耽误。今天就从一线经验出发,告诉你南阳电工证换证的全盘操作,还有这证到底还有没有含金量。… · 2026/11/23 4:23:19

特种工6个月全流程办理指南:上岗必备怎么搞定
特种工6个月全流程办理指南:上岗必备怎么搞定

特种工6个月全流程办理指南:上岗必备怎么搞定 你是不是正盯着手机里的招聘信息,心里直打鼓?“特种作业证还没拿到,这工作能不能顺利上岗?”别急,特种工6个月全流程办理其实没你想象的那么难,关键是要知道怎么走流程,怎么准备,怎么应对考试。这篇文… · 2026/11/23 4:23:19

低压电工证科目二模拟怎么考过?真实经历告诉你通过率有多高
低压电工证科目二模拟怎么考过?真实经历告诉你通过率有多高

低压电工证科目二模拟怎么考过?真实经历告诉你通过率有多高 你是不是也像我一样, 急需特种作业证才能上岗找工作 ?低压电工证科目二模拟考试是很多电工新手最头疼的环节。今天我就从自己的真实经历出发,和你聊聊怎么才能顺利通过低压电工证科目二模拟考… · 2026/11/23 4:23:19

建筑电工证西安怎么补办 电子证书能跨省转移吗
建筑电工证西安怎么补办 电子证书能跨省转移吗

建筑电工证西安怎么补办 电子证书能跨省转移吗 之前考的证在外省能不能转过来?这个问题其实很多人在问,尤其是在西安从事建筑电工行业的小伙伴。尤其是很多从外地过来工作,或者已经在外地考了证,但想在西安继续从事相关工作的朋友,都想知道自己手里的证… · 2026/11/23 4:23:19

电厂上班要电工证怎么报名?网上查询流程别走弯路
电厂上班要电工证怎么报名?网上查询流程别走弯路

电厂上班要电工证怎么报名?网上查询流程别走弯路 怕考不过白交培训费?别让培训费打水漂!你不是一个人在战斗,我见过太多人因为选错了培训机构,浪费了几千块培训费,结果连考试都没通过。今天我就从一个在商丘初次报考电工证的视角,给你讲清楚怎么通过… · 2026/11/23 4:23:19

电工证维护和运行区别,多久拿证?学历不高也能考!
电工证维护和运行区别,多久拿证?学历不高也能考!

电工证维护和运行区别,多久拿证?学历不高也能考! 你是不是也担心自己学历不高,报不了电工证?别急,我来告诉你真相。电工证虽然分“维护”和“运行”两类,但报考门槛其实并不高,只要符合基本条件, 多久拿证… · 2026/11/23 4:22:19

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定
平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定 你是不是也经常在网上看到“平价的电工证查询”这样的关键词,但又不知道去哪报名,怕被中介坑?特别是像你这样的平顶山学员,既想考个正规电工证,又怕花冤枉钱走弯路。别担心,这篇保姆级教程就是… · 2026/11/23 1:57:37

麻阳考电工证在哪里考内部消息你知道吗
麻阳考电工证在哪里考内部消息你知道吗

麻阳考电工证在哪里考内部消息你知道吗 不知道去哪报名怕被中介坑, 内部消息 告诉你,麻阳考电工证不一定要去外地,本地其实也有正规渠道,但很多人因为不了解流程和资质,反而被坑了钱还考不到证。今天我就从一个干了这么多年特种作业培训的“老江湖”角… · 2026/11/23 1:54:31

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程
揭阳普宁电工证换证怎么操作?良心建议帮你理清流程

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程 之前考的证在外省能不能转过来?这是很多已经在外地工作、现在想回揭阳普宁发展的电工朋友最关心的问题。如果你也是其中之一,那这篇文章就是为你们量身定制的,从换证流程到避坑建议,良心建议全给你讲透… · 2026/11/23 2:28:29

工地太忙根本没时间复习考试?泗阳电工证快速办理内部消息全在这了
工地太忙根本没时间复习考试?泗阳电工证快速办理内部消息全在这了

工地太忙根本没时间复习考试?泗阳电工证快速办理内部消息全在这了 工地太忙根本没时间复习考试,尤其是像你这样在信阳水利工程一线打拼的老电工,天天跟钢筋水泥打交道,哪还有空去背那些考试题?更别提现在办证流程越来越复杂,稍有不慎就可能耽误项目进度… · 2026/11/23 0:00:44

低压电工证复证材料千万别踩坑!这些材料你准备好了吗?
低压电工证复证材料千万别踩坑!这些材料你准备好了吗?

低压电工证复证材料千万别踩坑!这些材料你准备好了吗? 证书过期了不知道怎么复审延期?你不是一个人!现在不少电工朋友都在为低压电工证复证材料发愁,怕流程复杂、怕材料不全、怕耽误工作。其实,只要准备充分,复审一点都不难。今天就来带你一步步搞清楚… · 2026/11/23 0:00:44

上海哪里考电工证便宜真实经历分享:实操考试心里没底怕挂科
上海哪里考电工证便宜真实经历分享:实操考试心里没底怕挂科

上海哪里考电工证便宜真实经历分享:实操考试心里没底怕挂科 实操考试心里没底怕挂科,这是很多准备考电工证的朋友的共同心声。尤其是在上海这样的大城市,报考渠道多、价格不一,很多人在报名前都会犹豫到底该去哪家机构,费用多少才算合理。我自己在驻马店… · 2026/11/23 0:00:44

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/22 20:41:13

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/23 3:25:38

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/22 23:39:58

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码