59.배송센터 L로부터 모든 수요지점 1 ～ 6까지의 최단 경로 네트워크를 구성하였을 때, 구성된 네트워크의 전체 거리는?

① 11 km

정답: X

11km는 거리 합만 가장 작게 잇는 최소걸침나무(2를 5-2로 연결) 값이다 — 그러면 L에서 2까지 9km로 길어진다.

② 12 km

정답: O

L에서 가까운 순: 1 = 3, 4 = 1 경유 4, 3 = 1 경유 5, 2 = 1 경유 6(L-2 7보다 짧다), 6 = 4 경유 6, 5 = 6 경유 7 → 쓰인 구간 L-1 3 + 1-4 1 + 1-3 2 + 1-2 3 + 4-6 2 + 6-5 1 = 12km.

③ 13 km

정답: X

5를 6-5 1 대신 2-5 2로 이으면 13km가 되지만 L에서 5까지 8km라 7km 길보다 멀다.

④ 14 km

정답: X

5를 3-5 3으로 이으면 14km다 — L→1→3→5는 8km라 L→1→4→6→5 7km보다 멀다.

⑤ 15 km

정답: X

각 지점까지 가장 짧은 길만 모으면 12km라 15km는 더 먼 길을 섞은 값이다.