「Codeforces 70E」Information Reform
题目链接:Codeforces 70E
虽然已经是二十一世纪了,但是大众传媒在海象国并不普及,城市之间只能通过公路交流。海象国中任意两座城市之间有且只有一条路径,且每条道路的长度都是 $1$。
为了进行改革,将会选择一些城市作为信息中心,维护一个信息中心需要 $k$ 元钱。对于其他城市,他们将会从最近的信息中心获得消息,如果设两者直接的距离为 $len$,那么这将花费 $d_{len}$ 元钱。
请你求出一种方案使得花费最小,并求出每个城市会从哪个信息中心获得消息。
数据范围:$1\le n\le 180$,$1\le k\le 10^5$,$0\le d_i\le d_{i+1}\le 10^5$。