首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
admin
2018-04-25
28
问题
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
选项
A、875
B、1045
C、1285
D、1525
答案
B
解析
这是一个求最短哈密尔顿回路的问题。因为该图只有5个结点，比较简单，只需使用观察法就能很快得出正确答案。首先注意的是，在本图中所有的“三角形”线路都满足三角形边长的规则：“任何两边的和大于第三边”，因此凡是有直通的航线，就不要中转。假设从图的最上方那个城市开始，首先选择189，然后选择379(因为279+209＞379)，再选择69，179，最后选择229，则结果为189+379+69+179+229=1045。
转载请注明原文地址:https://kaotiyun.com/show/XxLZ777K
本试题收录于：
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
请向幻灯片的文本中添加第一种项目符号。
利用菜单操作，请将图表“销售情况”的分类轴设置字体颜色为红色，坐标轴加粗显示。
请同时调整3个列的列宽，使其一致。
在光标所在的位置插入符号“①”。
请添加自定义项目符号中的第4行第2列作为当前文本的项目符号。
请为演示文稿添加自定义数字签名，名称为“tianyu”，目的为“加密”。
步骤1单击[公式]选项卡→[插入函数]按钮，在[选择函数]列表框中单击[SUMIF]→[确定]按钮，如图3—11所示。[*]步骤2单击[Range]处的图标按钮，选中单元格区域B3：B7。步骤3在[criteria]文本框
下列叙述中，不属于结构化程序设计方法的主要原则的是()。
数据库恢复是将数据库从()状态恢复到某一已知的正确状态。
在下列几种排序方法中，要求内存量最大的是()。
随机试题
新民主主义的三大经济纲领内容是()
某工程施工时，因业主原因造成某工作拖延1周，该工作具有5d总时差，3d自由时差，则承包商可获得工期索赔为()d。
背景A施工单位总承包某机电安装单项工程，该工程包含3个单位工程，其中泵房单位工程分包给B专业公司。进入工程后期，两个单位工程已经办理中间交接手续，其中A施工单位承包的1个单位工程中，有一台能量回收系统的燃气轮机组，因受介质限制而不能进行单机试运行
()素有“九寨精华”之称，是九寨沟各个景点中最受人关注和喜爱的。
下列语段中画横线的词语，使用不恰当的一项是()。哈佛大学教授杜维明说，“西方的人文学和人文主义基本上是反自然和反宗教，对自然有侵略的倾向，对宗教不闻不问。但儒家所代表的人文学要求人类既要和自然保持和谐，又要与宗教保持相辅相成的关系，所以它的内涵比
“世界上最宽阔的是海洋，比海洋更宽阔的是人的胸怀。”这句话启示我们与人交往要()。
深刻把握全面深化改革的路线图，要紧紧围绕提高()水平深化党的建设制度改革。
本文的作者是：给本文选择一个合适的标题：
Ifyouwanttobookahotelroom,youshoulddial______.WhattimecanIseewaterlifelikeeels?
AnOhioStateUniversitystudyhaslinkedbehaviorinyoungchildren【C1】______thetypeofjobtheirmotherhas.Motherswithcom
最新回复
(
0
)
