CF70E Information Reform

尽管现在已经是21世纪了，但是大众传播媒介在$Walrusland$依然没有普及开来。这里的城市通过能够在城市间的道路来往的信使来互相传递消息。在$Walrusland$，城市间的道路保证信使可以从一座城市到任意另一座城市，而且这些道路是等长的。 北极政府决定实施一项信息改革。几座城市被选中成为区域信息中心。维护一座区域信息中心每年需要花费$k$个$fishlar$（这是当地的货币）。假设每座区域信息中心总是能即时获得最新的消息。 每一座不是区域信息中心的城市，都会被安排通过一座区域信息中心来保持信息通达。这样，每年维护费用将会等于$d_{len} \ $个$fishlar$，其中$len$表示这座城市到它的区域信息中心的距离，即一个人从这座城市到它的区域信息中心需要走过的道路条数。 你的任务是求出实行这项改革的最小开销。

无

无