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

Problem - D - Codeforces

題意：
有 N 個城市，每對城市之間存在一個雙向路徑，每一條邊有一個死亡值 P。
一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。
對於每個城市 x，問一種方法，使得每個點對外都只留下一個有向邊，使得所有城市都會到達城市 x，且路徑死亡值總和最小。
對每個城市要求輸出這個總和。

制約：
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.

解法：
考慮最小的那個邊，令它的權值為 minw。為了方便，可以將所有邊的權值減去 minw，最後再加回 ( N - 1 ) * minw。
現在考慮這個新的圖，考慮目標存在一個鄰接邊的邊權為 0。那麼這張圖上的這個目標的答案是 0，因為可以讓所城市都直接指向這條邊這個目標的另一頭，而這另一頭再指回目標。現在考慮目標不存在一個鄰接邊的邊權為 0，那麼還是可以讓所有城市都直接指向邊權為 0 的邊的其中一個城市 u，那麼該邊另一頭城市 v 再指向目標，這時候的花費是 adj[ v ][ 目標 ]。但是，考慮這個 adj[ v ][ 目標 ] 可能太大，也許找一個適當的中繼點 k，adj[ v ][ k ] + adj[ k ][ 目標 ] 更好。這時候會發現，那也許比起 adj[ v ][ k ]，某個 adj[ v ][ x ] + adj[ x ][ k ] 又更好...。這時候想辦法規約成最短路徑的問題。令 dp[ x ] 為 x 的答案，我們有至少一個確定是正確的起點 -- 有邊權 0 的鄰接邊的任意一個 u。考慮 Dijkstra 式的轉移，轉移邊的兩種情況：
一、直接從 u 花費 adj[ u ][ v ] 走到 v
二、令 f = min( adj[ i ][ v ] for all i )，且 g 為滿足最小的 i ，則以 g 為中繼點從 u 走到 v。這個花費就記做 f * 2。如果 adj[ u ][ g ] ≥ adj[ g ][ v ] 那顯然是沒有問題的。否則，這是高估，而正確的 adj[ u ][ g ] + adj[ g ][ v ] 更新顯然會在將來發生。

時間 / 空間複雜度：
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;
  memset( adj, 0x3f, sizeof( adj ) );
  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 ) ) )