Innovative Consumer Products Company (ICPC)는 1급 비밀 프로젝트를 시작할 계획이다.

이 비밀 프로젝트는 s개의 하위 프로젝트로 구성된다.

이 비밀 프로젝트와 연관된 ICPC의 지사들은 b ≥ s 개이며,

ICPC는 각 지사에 하위 프로젝트들 중 하나를 맡기고자 한다.

다시 말해서, 지사들은 s개의 분리된 그룹으로 나누어지고, 각 그룹은 하나의 하위 프로젝트를 맡게 된다.

각 달의 마지막에, 각 지사는 그 그룹에 있는 다른 모든 지사에게 메시지를 보낼 것이다(서로 다른 지사에는 다른 메시지를 보낸다).

ICPC는 통신을 위한 특별한 프로토콜을 가지고 있다. 각 지사 i는 그 지사와 본부에만 공개된 비밀키 k_i를 가지고 있다.

지사 i가 지사 j에 메시지를 보내고 싶어한다고 하자. 지사 i는 비밀키 k_i로 메시지를 암호화한다.

신뢰할 수 있는 운반원이 이 메시지를 지사로부터 본부까지 전달한다.

본부는 키 k_i로 메시지를 복호화하고, 키 k_j로 다시 암호화시킨다.

운반원은 새롭게 암호화된 메시지를 (키 k_j를 가지고 있는) 지사 j로 전달한다.

보안적인 문제 때문에, 운반원은 동시에 오직 하나의 메시지만 전달할 수 있다.

도로망과 지사와 본부의 위치가 주어졌을 때, 당신은 각 지사에 하위 프로젝트를 배정하는 모든 경우에 대해서,

월말에 운반원이 메시지를 전달하기 위해 이동해야하는 최소 거리를 알아내야 한다.

지사배정(Branch Assignment) timer 3s memory 512MB

지사배정(Branch Assignment) 3s 512MB