72.물류센터에서 8곳 배송지까지 최단 경로 네트워크를 작성하였을 때, 그 네트워크의 총길이는?

① 150 km

정답: X

아홉 마디를 모두 잇는 가장 짧은 나무도 180km라 150km로는 다 이을 수 없다.

② 160 km

정답: X

모든 배송지를 잇는 데 180km보다 짧은 길은 없다 — 160km로는 한 곳이 남는다.

③ 170 km

정답: X

170km로는 여덟 배송지를 다 이을 수 없다 — 가장 짧게 이어도 180km다.

④ 180 km

정답: O

최단거리: 4=10, 7=20, 6=30, 1=4 거쳐 30, 8=4 거쳐 30, 5=8 거쳐 50, 2=1 거쳐 60, 3=2 거쳐 90 → 고른 링크 10 + 20 + 30 + 20 + 20 + 20 + 30 + 30 = 180km.

⑤ 190 km

정답: X

7을 센터에서 바로(20) 잇지 않고 4를 거쳐(4-7 30) 이으면 190km가 된다 — 7까지 최단거리는 20이다.