{"problem":{"name":"D. 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":"CF773D"},"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 intersect, and no road passes through intermediate cities. The art of building tunnels and bridges has been mastered by Neverians.\n\nAn 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.\n\nIt'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.\n\nNeverians 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.\n\nThe 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.\n\n## Input\n\nThe first line contains a single integer _n_ (2 ≤ _n_ ≤ 2000) — the number of cities in Never.\n\nThe 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_.\n\nAll road perishabilities are between 1 and 109, inclusive.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nThe 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.\n\nFor 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.\n\n<center>![image](https://espresso.codeforces.com/27d3608236ddddddce1675789a01a3aacdb4b0cf.png)</center>","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_span(class=[tex-font-style-underline], body=[perishability])。公路的 perishability 越低，驾车通过该公路就越愉快。\\n\\n今年是Never国的交通年。决定在其中一座城市建造一座交通博物馆，并在其他每座城市设置一个指路牌，指向某座城市（不一定是有博物馆的城市）。这些指路牌必须满足以下重要条件：如果任何居住在没有博物馆的城市的Never人从该城市出发，严格按照指路牌的方向行驶，最终一定会到达有博物馆的城市。\\n\\nNever人极其乐观。如果一个Never人沿着由若干条公路组成的路线旅行，他将这条路线的 #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。\\n\"},{\"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。  \"}]\n\n```json\n[{\"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国的交通年。决定在其中一座城市建造一座交通博物馆，并在其他每座城市设置一个指路牌，指向某座城市（不一定是有博物馆的城市）。这些指路牌必须满足以下重要条件：如果任何居住在没有博物馆的城市的Never人从该城市出发，严格按照指路牌的方向行驶，最终一定会到达有博物馆的城市。\\n\\nNever人极其乐观。如果一个Never人沿着由若干条公路组成的路线旅行，他将这条路线的 #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。\\n\"},{\"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。  \"}]\n```","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 \\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 $.\n\n**Constraints**  \n1. The graph $ G $ is complete: $ |E| = \\binom{n}{2} $.  \n2. All edge weights satisfy $ 1 \\leq w(i,j) \\leq 10^9 $.  \n3. For each candidate museum city $ m \\in V $, a directed spanning tree (arborescence) $ T_m $ rooted at $ m $ must be chosen such that:  \n   - Every vertex $ v \\neq m $ has out-degree 1.  \n   - There is a unique directed path from every $ v \\neq m $ to $ m $.  \n\n**Objective**  \nFor each $ m \\in \\{1, 2, \\dots, n\\} $, define the *route perishability* from vertex $ v \\neq m $ to $ m $ as the minimum edge weight along the unique directed path from $ v $ to $ m $ in $ T_m $.  \nLet $ S(m) = \\sum_{v \\neq m} \\min_{e \\in P_{v \\to m}} w(e) $, where $ P_{v \\to m} $ is the path from $ v $ to $ m $ in $ T_m $.  \n\nCompute $ \\min_{T_m} S(m) $ for each $ m \\in \\{1, \\dots, n\\} $, over all valid arborescences $ T_m $ rooted at $ m $.  \n\nOutput $ \\min_{T_1} S(1), \\min_{T_2} S(2), \\dots, \\min_{T_n} S(n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF773D","tags":["dp","graphs","shortest paths"],"sample_group":[["3\n1 2\n3","2\n2\n3"],["6\n2 9 9 6 6\n7 1 9 10\n9 2 5\n4 10\n8","6\n5\n7\n5\n7\n11"]],"created_at":"2026-03-03 11:00:39"}}