문제

알고치킨은 요즘 가장 떠오르는 스타트업 치킨 업체이다. 그 비결은 잘 튀겨낸 치킨에도 있지만, 국내 요식업에서 빼놓을 수 없는 배달 비용을 최소화하여 치킨 가격을 낮춰낸 것이 유효했다.

알고치킨의 치킨 배달 방식은 상당히 독특한데, 다음과 같다:

1. 알고치킨이 존재하는 도시는 그래프의 형태로 주어지며, 알고치킨의 체인점과 고객들은 각 정점 위에 존재할 수 있다.
2. 고객은 특정 알고치킨 체인점에 전화하여 치킨을 주문할 수 있다.
3. 모든 체인점의 알고치킨은 동일한 품질을 유지하는 것에 굉장히 노력을 기울여, 그 결과 어느 체인점에서 해당 고객에게 배달을 하더라도 고객은 늘 만족할 수 있게 되었다.
4. 물론 고객들은 자신이 지정한 특정 맛집에서 배달을 받는다고 믿고 있다. 따라서 만약 고객이 지정한 체인점에서 고객까지 배달할 수 있는 길이 없다면 해당 주문은 무시된다.
5. 각 체인점 사장님들의 수익 보전을 위해 각 체인점은 받은 주문 수 만큼의 발주를 하고 싶어한다.

위와 같은 성질을 이용하여 많은 주문이 들어올 경우 알고치킨은 고객이 선택한 체인점과 실제 배송을 담당하는 체인점을 잘 조율하여 배송 비용을 최적화 할 수 있다. 배송 비용이란 모든 주문들을 배송하는데 드는 체인점으로부터 고객까지의 거리의 합과 같다.

당신은 알고치킨의 데이터 분석가로써 현 알고치킨 알고리즘에 대해 개선안을 제안해야 하는 위치에 놓였다. 그 첫번째 단계로, 도시 정보와 주문 정보들이 주어질 때 각 경우에 대하여 최적의 배송 비용을 알아내자.