P6918 [ICPC 2016 WF] Branch Assignment

The Innovative Consumer Products Company (ICPC) is planning to start a top-secret project. This project consists of $s$ subprojects. There will be $b \ge s$ branches of ICPC involved in this project and ICPC wants to assign each branch to one of the subprojects. In other words, the branches will form $s$ disjoint groups, with each group in charge of a subproject. At the end of each month, each branch will send a message to every other branch in its group (a different message to each branch). ICPC has a particular protocol for its communications. Each branch $i$ has a secret key $k_ i$ known only to the branch and the ICPC headquarters. Assume branch $i$ wants to send a message to branch $j$. Branch $i$ encrypts its message with its key $k_ i$. A trusted courier picks up this message from this branch and delivers it to the ICPC headquarters. Headquarters decrypts the message with key $k_ i$ and re-encrypts it with key $k_ j$. The courier then delivers this newly encrypted message to branch $j$, which decrypts it with its own key $k_ j$. For security reasons, a courier can carry only one message at a time. Given a road network and the locations of branches and the headquarters in this network, your task is to determine the minimum total distance that the couriers will need to travel to deliver all the end-of-month messages, over all possible assignments of branches to subprojects.

无

无

Time limit: 2000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2016