问题
单项选择题
已知某山区六个乡镇C1,C2,…,C6之间的公路距离(公里数)如下表:
C1 | C2 | C3 | C4 | C5 | C6 | |
C1 | 0 | 50 | ∞ | 40 | 25 | 10 |
C2 | 50 | 0 | 15 | 20 | ∞ | 25 |
C3 | ∞ | 15 | 0 | 10 | 20 | ∞ |
C4 | 40 | 20 | 10 | 0 | 10 | 30 |
C5 | 25 | ∞ | 20 | 10 | 0 | 25 |
C6 | 10 | 25 | ∞ | 30 | 25 | 0 |
其中符号“∞”表示两个乡镇之间没有直通公路。乡镇C1到C3虽然没有直通公路,但可以经过其他乡镇达到,根据上表,可以算出C1到C3最短的路程为()公里。
A.35
B.40
C.45
D.50
答案
参考答案:C
解析:
[分析]: 本题考查图论应用基础知识。
根据题中给出的6个乡镇间的公路距离表,可以绘制距离图如下:
[*]
结点①、②、…、⑥分别表示这6个乡镇,结点之间的连线表示有公路直接通达,连线上的数字表示公里数。从图可以看出,乡镇①到③没有直通公路,但可以通过其他乡镇达到。显然,路径①-⑤-④-③总的里程数45公里是最短的。