题目描述

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.

输入格式

The first line of input contains four integers $n$, $b$, $s$, and $r$, where $n$ ($2 \le n \le 5\, 000$) is the number of intersections, $b$ ($1 \le b \le n-1$) is the number of branches, $s$ ($1 \le s \le b$) is the number of subprojects, and $r$ ($1 \le r \le 50\, 000$) is the number of roads. The intersections are numbered from $1$ through $n$. The branches are at intersections $1$ through $b$, and the headquarters is at intersection $b + 1$. Each of the next $r$ lines contains three integers $u$, $v$, and $\ell$, indicating a one-way road from intersection $u$ to a different intersection $v$ ($1 \leq u,v \leq n$) of length $\ell$ ($0 \leq \ell \leq 10\, 000$). No ordered pair $(u,v)$ appears more than once, and from any intersection it is possible to reach every other intersection.

输出格式

Display the minimum total distance that the couriers will need to travel.

题目大意

题目描述

给定一个 $n$ 个点，$r$ 条边的有向强连通图，正整数 $s,b$ 满足 $1\le s\le b \le n-1$。第 $b+1$ 个点称为总部。点 $x$ 向点 $y$ 发送信息的代价是 $dis(x,b+1)+dis(b+1,y)$。
现将点集 $\{1,2,\cdots,b\}$ 划分为 $s$ 个不相交的子集 $S_1,S_2,\cdots,S_s$。同一个子集内的点两两之间会互相发送信息。求最小化总代价。

数据范围

$2\le n \le 5000$，$1\le s\le b\le n-1$，$1\le r\le 50000$，边权非负且不大于 $10000$。

5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

13

5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 10
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

24

提示

Time limit: 2000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2016