Perishable Roads
Contest: VK Cup 2017 - Round 3
Difficulty rating: 2700
Tags: dp, graphs, shortest paths

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 $$\frac{n(n-1)}{2}$$ 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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
3
1 2
3

Example output:
2
2
3

Example input:
6
2 9 9 6 6
7 1 9 10
9 2 5
4 10
8

Example output:
6
5
7
5
7
11

Editorial:
This is my favorite problem in this contest. Several clever observations make its solution really simple.
First important observation helps understand the optimal structure of the signpost directions. Suppose there are two cities A and B with the signposts directed to the same city C. Without loss of generality, suppose that the road A-C has smaller or equal perishability than the road B-C. Then, if the signpost in city B is redirected to city A instead, perishability of the route from B (as well as from other cities with routes passing through B) to the museum city won't increase. It follows that there exists an optimal solution with at most one signpost directing to each city, so the directions of the signposts form a path ending in the museum city.
Second important observation is that there exists a road with the smallest perishability p. Let's subtract p from all road perishabilities, and increase the answer by p·(n - 1) in the end. Now, all roads have non-negative perishabilities, and there exists a road with perishability 0. Once our path contains such a road, perishabilities of all routes from cities after this road up the path is equal to 0.
More formally, let's denote perishabilities of the roads in the path starting from the museum city as w1, w2, ..., wn - 1. The sought sum is then equal to $$\sum_{i=1}^{n-1}\min_{j=1}^i w_j$$. It's easy to prove that there exists some k such that wk = 0. Indeed, as we go up the path from the museum city, then once we visit an endpoint of any 0-perishability road it's good to follow this 0-perishability road so that route perishabilities of all the remaining cities become 0.
Consider an optimal solution, and let k be the smallest index with wk = 0. Let's prove that for all i ≤ k - 3 we have wi > wi + 1. Indeed, assume that for some i ≤ k - 3 we have wi ≤ wi + 1. Then, since the graph is complete, we can replace the i + 1-th edge with an edge directing to an endpoint of any 0-perishability road, and the i + 2-th edge with this 0-perishability road. In this case, the minimized sum will become smaller, which is a contradiction to our solution being optimal.
Then, we have two options: either wk - 2 > wk - 1 or wk - 2 ≤ wk - 1. If some path of the first type is optimal, then it always coincides with the minimum weight path from the museum city to some city adjacent to a 0-perishability road, and the weight of this path will be the answer. If some path of the second type is optimal, then in this path we first move to some city X, and then use two roads to move to a city adjacent to a 0-perishability road, and we increase the answer by double the weight of the first of these roads as the result of this movement — therefore, first we find the minimum weight path from the museum city to each city X, increase the weight of this path by double the smallest perishability of the roads adjacent to X, and find the answer as the smallest of these values.
This gives us an O(n3) solution if we run Dijkstra's algorithm from every vertex of the graph to find the answer for it.
It can be optimized to O(n2) if instead of running Dijkstra's algorithm from every vertex, we run just one instance of Dijkstra's algorithm, initializing the answer for each vertex with double the smallest perishability of an adjacent edge.