问题 单项选择题

已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:

 C1C2C3C4C5C6
C1050402510
C2500152025
C31501020
C440201001030
C5252010025
C6102530250

其中符号“∞”表示两个乡镇之间没有直通公路。乡镇C1到C3虽然没有直通公路,但可以经过其他乡镇达到,根据上表,可以算出C1到C3最短的路程为()公里。

A.35

B.40

C.45

D.50

答案

参考答案:C

解析:

[分析]: 本题考查图论应用基础知识。

根据题中给出的6个乡镇间的公路距离表,可以绘制距离图如下:

[*]

结点①、②、…、⑥分别表示这6个乡镇,结点之间的连线表示有公路直接通达,连线上的数字表示公里数。从图可以看出,乡镇①到③没有直通公路,但可以通过其他乡镇达到。显然,路径①-⑤-④-③总的里程数45公里是最短的。

选择题
问答题 简答题