# CFR 806 D. Perishable Roads ( Shortest Path, Graph )

Problem - D - Codeforces

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 1e9, inclusive.

O( N ** 2 )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000;
const int INF = 0x3f3f3f3f;

int N;
int adj[ MAXN ][ MAXN ];
int minw = INF;
int cost[ MAXN ][ MAXN ];
int dp[ MAXN ];
int vis[ MAXN ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N - 1; ++i ) {
for( int j = 0; j < N - 1 - i; ++j ) {
cin >> adj[ i ][ i + j + 1 ];
minw = min( minw, adj[ i + j + 1 ][ i ] = adj[ i ][ i + j + 1 ] );
}
}
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < i; ++j ) {
adj[ i ][ j ] -= minw;
adj[ j ][ i ] -= minw;
}
}
for( int i = 0; i < N; ++i ) {
int whole = INF;
for( int j = 0; j < N; ++j ) {
whole = min( whole, adj[ j ][ i ] );
}
for( int j = 0; j < N; ++j ) {
cost[ j ][ i ] = min( adj[ j ][ i ], whole * 2 );
}
}
memset( dp, 0x3f, sizeof( dp ) );
for( int i = 0; i < N; ++i ) {
int mind = INF;
for( int j = 0; j < N; ++j ) {
mind = min( mind, adj[ i ][ j ] );
}
dp[ i ] = mind * 2;
}
for( int i = 0; i < N; ++i ) {
int mind = INF, u;
for( int j = 0; j < N; ++j ) {
if( vis[ j ] ) continue;
if( mind > dp[ j ] ) {
mind = dp[ j ];
u = j;
}
}
vis[ u ] = 1;
for( int j = 0; j < N; ++j ) {
dp[ j ] = min( dp[ j ], dp[ u ] + cost[ u ][ j ] );
}
}
for( int i = 0; i < N; ++i ) {
cout << 1LL * minw * ( N - 1 ) + dp[ i ] << "\n";
}
return 0;
}
```
```# TLE
# But it's beautiful
N = int( input() )
adj = [ [ int( 1e9 ) for i in range( N ) ] for j in range( N ) ]
for i in range( N - 1 ):
d = list( map( int, input().split() ) )
for j in range( N - 1 - i ):
adj[ i ][ i + j + 1 ], adj[ i + j + 1 ][ i ] = d[ j ], d[ j ]

minw = min( list( map( min, adj ) ) )
for i in range( N ):
for j in range( i ):
adj[ i ][ j ] -= minw
adj[ j ][ i ] -= minw

cost = [ [ adj[ i ][ j ] for j in range( N ) ] for i in range( N ) ]
for i in range( N ):
whole = min( adj[ j ][ i ] * 2 for j in range( N ) )
for j in range( N ):
cost[ j ][ i ] = min( cost[ j ][ i ], whole )

dp = [ 2 * min( adj[ i ] ) for i in range( N ) ]
vis = [ False for i in range( N ) ]
for i in range( N ):
mind = min( dp[ x ] for x in range( N ) if not vis[ x ] )
u = min( x for x in range( N ) if not vis[ x ] and dp[ x ] == mind )
vis[ u ] = True
for j in range( N ):
dp[ j ] = min( dp[ j ], dp[ u ] + cost[ u ][ j ] )

print( '\n'.join( map( lambda x: str( x + ( N - 1 ) * minw ), dp ) ) )
```