CSP-S 2021 第一轮 第15题：有如下的有向图，节点为A，B，…，J，其中每条边的长度都标在图中。则节点A到节

题目

有如下的有向图，节点为 $A ,B , \cdots , J$, 其中每条边的长度都标在图中。则节点 $A$ 到节点 $J$ 的最短路径长度为（ ）。

选项

• A. 16
• B. 19
• C. 20
• D. 22

答案

B

题解

选 B．19。

按图中从左到右的顺序，逐层计算从 \(A\) 到各节点的最短距离。规则是：到达某个节点，比较所有“前一个节点的最短距离＋连接边的长度”，取最小值。

第一层： \[ d(B)=2,\qquad d(C)=5,\qquad d(D)=1. \]

第二层： \[ \begin{aligned} d(E)&=\min(2+12,\ 5+6,\ 1+13)=11,\\ d(F)&=\min(2+14,\ 5+10,\ 1+12)=13,\\ d(G)&=\min(2+10,\ 5+4,\ 1+11)=9. \end{aligned} \]

第三层： \[ \begin{aligned} d(H)&=\min(11+3,\ 13+6,\ 9+8)=14,\\ d(I)&=\min(11+9,\ 13+5,\ 9+10)=18. \end{aligned} \]

最后： \[ d(J)=\min(14+5,\ 18+2)=\boxed{19}. \]

对应的最短路径为 \(A\to C\to E\to H\to J\)，长度为 \(5+6+3+5=19\)。