首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
admin
2018-04-25
64
问题
设如图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
系统分析师上午综合知识考试
软考高级
相关试题推荐
请将两层组织结构图中，第一层定义为职称，第二层图框分别定义为教授、副教授和讲师。
请在当前幻灯片中，复制已选择的图形对象。
在表格第一行第一列的单元格中设置斜线表头，要求使用第一种斜线类型。
自定义编号，样式为“甲、,乙、,丙、”。
首先查看Sheet1工作表中的数据，在相应当前单元格中输入公式使用相对引用计算出各产品的总销售额。
数据库系统的核心是()。
在单链表中，增加头结点的目的是()。
在程序设计阶段应该采取（）和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。
在下列几种排序方法中，要求内存量最大的是()。
以下有关运算符重载的叙述中，正确的是________。
随机试题
A,胸腺瘤B,畸胎瘤C,淋巴肉瘤D,神经纤维瘤E,纵隔囊肿首先放射治疗
患儿，男，7岁。下前牙长出“双排牙”。经检查，前排牙松动Ⅰ度。后排牙位于牙列舌侧。引起下前牙区“双排牙”的常见原因是
患儿，5岁，因水痘被妈妈带来医院，水痘皮疹的特点是
以下不是公积金个人住房贷款的特点的是()。
甲企业为增值税一般纳税人，2018年10月发生下列经济业务：(1)购进油漆，用于装饰本企业办公楼，取得的普通发票上注明金额4000元。(2)购进办公用复印纸，取得的增值税专用发票上注明价款3000元。(3)购进生产用原材料，取得普通发票，支付价税
支票的出票人在支票上未加盖与该单位在银行预留签章一致的财务专用章而加盖该出票人公章的，签章人应当承担票据责任。()
设f(χ)二阶可导，且＝0，f(1)＝1，证明：存在ξ∈(0，1)，使得ξf〞(ξ)＋2f′(ξ)＝0．
Readthefollowingletter.Arethesentences(16-22)"Right"or"Wrong"?Ifthereisnotenoughinformationtoanswer"right"o
Wepackedearly.An8a.m.internationalflight,especiallyonetobetakenwithchildren,demandsstrictattentiontodetailan
Youshouldspendabout20minutesonQuestions1-13,whicharebasedonReadingPassage1below.Thecon
最新回复
(
0
)
