设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。A．875B．1045C．1285D．1525

题目

设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

A．875

B．1045

C．1285

D．1525

相似考题

1.对于五城市旅行商问题，求从A出发经B、C、D、E再回到A的最短路径。如果用s表示当前状态，L(s)表示已经走过的城市数，Goto(x)表示走向城市x，则其规则可以表示为：1，IFL(s)=5THENGoto(A);2，IFL(s)A、(2)B、(2)(3)C、(2)(3)(4)D、(2)(3)(4)(5)

2.根据权值集合{0.30,0.25,0.25,0.12,0.08}构造的哈夫曼树中,每个权值对应哈夫曼树中的一个叶结点()A.根结点到所有叶结点的路径长度相同 B.根结点到权值0.30和0.25所表示的叶结点路径长度相同 C.根结点到权值0.30所表示的叶结点路径最长 D.根结点到权值0.25所表示的两个叶结点路径长度不同

3.设A城市至B城市客运运价里程为263Km,查表得知：1~200Km的票价率为0.05861（元*人-1*km-1），201~500km的票价率为 0.05275（元*人-1*km-1），该例运费里程属于201~400km区段，该区段间距为20km,A市至B市的票价里程为261~280km的 中间里程，即270km。 A市至B市硬座票价全价为（）元。 A.20 B.16.7 C.16 D.15 E.10

4.下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用（百元/车）。城市A有三个装货点，城市B有三个卸货点，各点旁标注的数字表示装/卸煤所需的费用（百元/车）。根据该图，从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为（ ）（百元/车）。A.19 B.20 C.21 D.22

参考答案和解析
正确答案：B
解析：这是一个求最短哈密尔顿回路的问题。因为该图只有5个结点，比较简单，只需使用观察法就能很快得出正确答案。首先注意的是，在本图中所有的“三角形”线路都满足三角形边长的规则：“任何两边的和大于第三边”，因此凡是有直通的航线，就不要中转。假设从图的最上方那个城市开始，首先选择189，然后选择379(因为279+209＞379)，再选择69，179，最后选择229，则结果为189+379+69+179+229=1045。
更多“ 设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。A．”相关问题

  • 第1题：

    设A城市至B城市客运运价里程为263Km,查表得知：1~200Km的票价率为0.05861（元*人-1*km-1），201~500km的票价率为 0.05275（元*人-1*km-1），该例运费里程属于201~400km区段，该区段间距为20km,A市至B市的票价里程为261~280km的 中间里程，即270km。
    A市至B市的基本票价为（）元。

    A.20
    B.15.4
    C.14.8
    D.14
    E.10

    答案：B
    解析：

  • 第2题：

    5.两个城市之间是否有航班直达用矩阵A表示，矩阵A是一个01矩阵（元素只有0和1），aij=0，表示i到j没有直达航班，aij=1表示i到j有航班直达，那么一下表述正确的是（） A.A^2表示两城市之间有航班直达; B.A^2+A表示2次航线之内两城市可以互达; C.A^2表示2次航线内可以达到的城市; D.A^2表示2次航线之内俩城市可以互达


    B

  • 第3题：

    两个城市之间是否有航班直达用矩阵A表示，矩阵A是一个01矩阵（元素只有0和1），aij=0表示i到j没有直达航班，aij=1表示i到j有航班直达，那么以下表述正确的是（） A.A^2表示两城市之间有航班直达; B.A^2+A表示2次航线之内两城市可以互达; C.A^2表示2次航线内可以达到的城市; D.A^2表示2次航线之内俩城市可以互达


    城市对型

  • 第4题：

    下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用（百元/车）。城市A有三个装货点，城市B有三个卸货点，各点旁标注的数字表示装/卸煤所需的费用（百元/车）。根据该图，从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为（56）（百元/车）。

    A.19
    B.20
    C.21
    D.22

    答案：A
    解析：
    从A线出发经过中间5点可以到达B线。首先，很容易计算并标注各条路线从第5点到达B线并卸货的最少费用，可将其标注在相应的点旁。据此就容易计算并标注从第4点到达B线并卸货的最少费用，并将其标注在相应的点旁，依次类推。

    从A的下端出发，向上、上、下、上、上、下到达B的中间点，总费用=3+（2+2+3+2+2+3) + 2=19 (百元/车）最少。

  • 第5题：

    5、5.两个城市之间是否有航班直达用矩阵A表示，矩阵A是一个01矩阵（元素只有0和1），aij=0，表示i到j没有直达航班，aij=1表示i到j有航班直达，那么一下表述正确的是（） A.A^2表示两城市之间有航班直达; B.A^2+A表示2次航线之内两城市可以互达; C.A^2表示2次航线内可以达到的城市; D.A^2表示2次航线之内俩城市可以互达


    Direct light

相关内容