65.다음 S에서 출발하여 F에 도착하는 운송네트워크의 최단경로 거리(km)는? (단, 경로별 숫자는 km임)

① 11

정답: X

11은 E까지의 최단거리다 — F로 가려면 E→F 1을 더해야 한다.

② 12

정답: O

S에서 A 4·B 6, D = A 4 + 3 = 7, C = D 7 + 1 = 8, E = C 8 + 3 = 11, F = E 11 + 1 = 12 → S→A→D→C→E→F = 4 + 3 + 1 + 3 + 1 = 12.

③ 13

정답: X

S→A→D→F(4 + 3 + 6)나 S→A→D→C→F(4 + 3 + 1 + 5)로 가면 13이 나온다.

④ 14

정답: X

S→B→C→E→F(6 + 4 + 3 + 1)로 가면 14가 나온다 — C에는 S→A→D→C로 가야 더 짧다.

⑤ 15

정답: X

S→B→E→F(6 + 8 + 1)로 가면 15가 나온다.