English · Original
Chinese · Translation
Formal · Original
In the country of Never, there are _n_ cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as roads! No two roads intersect, and no road passes through intermediate cities. The art of building tunnels and bridges has been mastered by Neverians.
An independent committee has evaluated each road of Never with a positive integer called the perishability of the road. The lower the road's perishability is, the more pleasant it is to drive through this road.
It's the year of transport in Never. It has been decided to build a museum of transport in one of the cities, and to set a single signpost directing to some city (not necessarily the one with the museum) in each of the other cities. The signposts must satisfy the following important condition: if any Neverian living in a city without the museum starts travelling from that city following the directions of the signposts, then this person will eventually arrive in the city with the museum.
Neverians are incredibly positive-minded. If a Neverian travels by a route consisting of several roads, he considers the perishability of the route to be equal to the smallest perishability of all the roads in this route.
The government of Never has not yet decided where to build the museum, so they consider all _n_ possible options. The most important is the sum of perishabilities of the routes to the museum city from all the other cities of Never, if the travelers strictly follow the directions of the signposts. The government of Never cares about their citizens, so they want to set the signposts in a way which minimizes this sum. Help them determine the minimum possible sum for all _n_ possible options of the city where the museum can be built.
## Input
The first line contains a single integer _n_ (2 ≤ _n_ ≤ 2000) — the number of cities in Never.
The following _n_ - 1 lines contain the description of the road network. The _i_\-th of these lines contains _n_ - _i_ integers. The _j_\-th integer in the _i_\-th line denotes the perishability of the road between cities _i_ and _i_ + _j_.
All road perishabilities are between 1 and 109, inclusive.
## Output
For each city in order from 1 to _n_, output the minimum possible sum of perishabilities of the routes to this city from all the other cities of Never if the signposts are set in a way which minimizes this sum.
[samples]
## Note
The first example is explained by the picture below. From left to right, there is the initial road network and the optimal directions of the signposts in case the museum is built in city 1, 2 and 3, respectively. The museum city is represented by a blue circle, the directions of the signposts are represented by green arrows.
For instance, if the museum is built in city 3, then the signpost in city 1 must be directed to city 3, while the signpost in city 2 must be directed to city 1. Then the route from city 1 to city 3 will have perishability 2, while the route from city 2 to city 3 will have perishability 1. The sum of perishabilities of these routes is 3.
<center></center>
[{"iden":"statement","content":"在Never国，有#cf_span[n]座城市和一个发达的公路系统。每对城市之间恰好有一条双向公路，因此总共有#cf_span[\\frac{n(n-1)}{2}]条公路！没有任何两条公路相交，也没有任何公路经过中间城市。Never人已经掌握了建造隧道和桥梁的艺术。\n\n一个独立委员会为每条公路赋予了一个正整数，称为该公路的#cf_span(class=[tex-font-style-underline], body=[perishability])。公路的perishability越低，驾驶通过该公路就越愉快。\n\n今年是Never国的交通年。决定在其中一座城市建造一座交通博物馆，并在其他每座城市设置一个指向某座城市（不一定是博物馆所在城市）的单一指示牌。这些指示牌必须满足以下重要条件：如果任何住在非博物馆城市的人从该城市出发，沿着指示牌的方向旅行，那么他最终会到达博物馆所在的城市。\n\nNever人极其乐观。如果一个人沿着由多条公路组成的路线旅行，他会将这条路线的#cf_span(class=[tex-font-style-underline], body=[perishability of the route])定义为该路线中所有公路的perishability的最小值。\n\nNever政府尚未决定在何处建造博物馆，因此他们考虑所有#cf_span[n]种可能的选项。最重要的指标是：当旅行者严格遵循指示牌方向时，从所有其他城市到博物馆所在城市的路线的perishability之和。政府关心其公民，因此希望以最小化该总和的方式设置指示牌。请帮助他们确定：当博物馆建在每座城市时，该总和的最小可能值。\n\n第一行包含一个整数#cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——Never国的城市数量。\n\n接下来的#cf_span[n - 1]行描述了公路网络。第#cf_span[i]行包含#cf_span[n - i]个整数。第#cf_span[i]行的第#cf_span[j]个整数表示城市#cf_span[i]与城市#cf_span[i + j]之间公路的perishability。\n\n所有公路的perishability均介于#cf_span[1]和#cf_span[10^9]之间（含）。\n\n请按城市编号从1到#cf_span[n]的顺序，输出：当博物馆建在该城市时，从所有其他城市到该城市的路线的perishability之和的最小可能值。\n\n第一个示例由下图解释。从左到右，分别是初始公路网络，以及博物馆分别建在城市1、2和3时指示牌的最优方向。博物馆所在城市用蓝色圆圈表示，指示牌方向用绿色箭头表示。\n\n例如，若博物馆建在城市3，则城市1的指示牌必须指向城市3，城市2的指示牌必须指向城市1。此时，从城市1到城市3的路线的perishability为2，从城市2到城市3的路线的perishability为1。这两条路线的perishability之和为3。"},{"iden":"input","content":"第一行包含一个整数#cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——Never国的城市数量。接下来的#cf_span[n - 1]行描述了公路网络。第#cf_span[i]行包含#cf_span[n - i]个整数。第#cf_span[i]行的第#cf_span[j]个整数表示城市#cf_span[i]与城市#cf_span[i + j]之间公路的perishability。所有公路的perishability均介于#cf_span[1]和#cf_span[10^9]之间（含）。"},{"iden":"output","content":"请按城市编号从1到#cf_span[n]的顺序，输出：当博物馆建在该城市时，从所有其他城市到该城市的路线的perishability之和的最小可能值。"},{"iden":"examples","content":"输入31 23输出223输入62 9 9 6 67 1 9 109 2 54 108输出6575711"},{"iden":"note","content":"第一个示例由下图解释。从左到右，分别是初始公路网络，以及博物馆分别建在城市1、2和3时指示牌的最优方向。博物馆所在城市用蓝色圆圈表示，指示牌方向用绿色箭头表示。例如，若博物馆建在城市3，则城市1的指示牌必须指向城市3，城市2的指示牌必须指向城市1。此时，从城市1到城市3的路线的perishability为2，从城市2到城市3的路线的perishability为1。这两条路线的perishability之和为3。 "}]"
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 2000 $, be the number of cities.
Let $ G = (V, E) $ be a complete graph with $ V = \{1, 2, \dots, n\} $, and edge weights $ w : E \to \mathbb{Z}^+ $, where $ w(i, j) $ is the perishability of the road between cities $ i $ and $ j $, given for all $ 1 \leq i < j \leq n $.
For a fixed museum city $ m \in V $, a *signpost configuration* is a directed tree $ T_m $ rooted at $ m $, with all edges oriented toward $ m $, such that every vertex $ v \ne m $ has out-degree 1 and there is a unique directed path from $ v $ to $ m $.
The *perishability of a path* from $ v $ to $ m $ is $ \min_{e \in \text{path}(v \to m)} w(e) $.
The *total cost* for museum at $ m $ is $ C(m) = \sum_{v \in V \setminus \{m\}} \min_{e \in \text{path}(v \to m)} w(e) $.
**Constraints**
The input provides the upper-triangular part of the weight matrix: for each $ i \in \{1, \dots, n-1\} $, the $ i $-th line contains $ n - i $ integers: $ w(i, i+1), w(i, i+2), \dots, w(i, n) $.
**Objective**
For each $ m \in \{1, 2, \dots, n\} $, compute:
$$
\min_{T_m} \sum_{v \ne m} \min_{e \in \text{path}_{T_m}(v \to m)} w(e)
$$
where the minimum is taken over all directed spanning trees $ T_m $ rooted at $ m $ with edges oriented toward $ m $.
API Response (JSON)
{
"problem": {
"name": "F. Perishable Roads",
"description": {
"content": "In the country of Never, there are _n_ cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as roads! No two roads int",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF807F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In the country of Never, there are _n_ cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as roads! No two roads int...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"在Never国，有#cf_span[n]座城市和一个发达的公路系统。每对城市之间恰好有一条双向公路，因此总共有#cf_span[\\\\frac{n(n-1)}{2}]条公路！没有任何两条公路相交，也没有任何公路经过中间城市。Never人已经掌握了建造隧道和桥梁的艺术。\\n\\n一个独立委员会为每条公路赋予了一个正整数，称为该公路的#cf_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 2000 $, be the number of cities. \nLet $ G = (V, E) $ be a complete graph with $ V = \\{1, 2, \\dots, n\\} $, and edge weights $ w : E \\to \\mat...",
"is_translate": false,
"language": "Formal"
}
]
}