← 返回题目列表

Codeforces · 773/D

D. 易腐烂的道路

中文机器翻译题面 查看原题

在Never国,有n个城市和发达的道路系统。每对城市之间恰好有一条双向道路,因此,总共有 $$\frac{n(n-1)}{2}$$ 道路!没有两条道路相交,也没有道路经过中间城市。内维安人掌握了建造隧道和桥梁的艺术。

一个独立委员会用一个正整数(称为道路的易腐性)评估了 Never 的每条道路。道路的腐烂率越低,开车通过这条道路的感觉就越愉快。

今年是Never 的交通年。已决定在其中一个城市建立一个交通博物馆,并在其他每个城市设置一个指向某个城市(不一定是有博物馆的城市)的单一路标。路标必须满足以下重要条件:如果任何居住在没有博物馆的城市的内维安人开始按照路标的指示从该城市出发,那么此人最终将到达有博物馆的城市。

内维安人的思想非常积极。如果一个Neverian人沿着一条由多条道路组成的路线旅行,他认为该路线的易损性等于该路线中所有道路的最小易损性。

Never政府还没有决定在哪里建造博物馆,所以他们考虑了所有n个可能的选择。最重要的是,如果旅行者严格遵循路标的指示,从讷讷所有其他城市到博物馆城市的路线的易损性总和。从不关心他们的公民,因此他们希望以尽量减少这笔费用的方式设置路标。帮助他们确定可以建造博物馆的城市的所有 n 个可能选项的最小可能总和。

输入

第一行包含一个整数 n (2 ≤ n ≤ 2000) — Never 中的城市数量。

以下 n - 1 行包含道路网络的描述。这些行的第 i 行包含 n - i 个整数。第 i 行中的第 j 个整数表示城市 i 和 i + j 之间的道路的易损性。

所有道路的易损性都在 1 到 109 之间(包含这两个值)。

输出

对于从 1 到 n 的每个城市,输出从 Never 的所有其他城市到该城市的路线的最小可能的易损性总和,如果路标的设置方式使该总和最小化。

示例

输入 #1

3
1 2
3

输出 #1

2
2
3

输入 #2

6
2 9 9 6 6
7 1 9 10
9 2 5
4 10
8

输出 #2

6
5
7
5
7
11

注意

第一个例子如下图所示。从左到右分别是博物馆建在1、2、3城市时的初始路网和路标的最佳方向。博物馆城市由蓝色圆圈表示,路标的方向由绿色箭头表示。

例如,如果博物馆建在城市3,那么城市1的路标必须指向城市3,而城市2的路标必须指向城市1。那么从城市1到城市3的路线的易腐性为2,而从城市2到城市3的路线的易腐性为1。这些路线的易腐性之和为3。