CFR 295 1B. Greg and Graph ( DP = Floyd Warshall + Reverse Thinking )

Problem - B - Codeforces
如果順著做，逐一破壞。。嗯，看到逐一破壞就可以開始想反著觀察就是逐一增加了。
因為問題是Multiple Source Shortest Path，所以可以馬上想到Floyd Warshall演算法了。
想起以前學長和我提過，為什麼三層迴圈的中繼點要在最外圈枚舉呢，訓練指南也有提過這點。因為事實上Floyd Warshall算法就是DP來的。轉移式是很有名的
dp[ k ][ i ][ j ] = min( dp[ k−1 ][ i ][ j ], dp[ k−1 ][ i ][ k ] + dp[ k−1 ][ k ][ j ] )
其中 k代表已考慮過前幾個點作為中繼點，i為起點，j為終點，是非常直觀的。
因此即使是動態加點動態查詢，只要實現這個轉移式就能O( n ^ 2 ) 維護了。
注意加入一個點之後不是馬上拿去當中繼，要先把它當作是集合裡的東西，把以它為起點或終點的所有路徑鬆弛一遍才行。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
const int MAXA = 1e5 + 5;
typedef long long ll;

int n;
int a[ MAXN ][ MAXN ];
int x[ MAXN ];
ll ans[ MAXN ];

ll dis[ MAXN ][ MAXN ];

void solve(){
    for( int i = 1; i <= n; ++i )
        for( int j = 1; j <= n; ++j )
            dis[ i ][ j ] = a[ i ][ j ];
    for( int i = n; i >= 1; --i ){
        for( int j = i; j <= n; ++j )
            for( int k = i; k <= n; ++k )
                if( dis[ x[ j ] ][ x[ i ] ] > dis[ x[ j ] ][ x[ k ] ] + dis[ x[ k ] ][ x[ i ] ] )
                    dis[ x[ j ] ][ x[ i ] ] = dis[ x[ j ] ][ x[ k ] ] + dis[ x[ k ] ][ x[ i ] ];
        for( int j = i; j <= n; ++j )
            for( int k = i; k <= n; ++k )
                if( dis[ x[ i ] ][ x[ j ] ] > dis[ x[ i ] ][ x[ k ] ] + dis[ x[ k ] ][ x[ j ] ] )
                    dis[ x[ i ] ][ x[ j ] ] = dis[ x[ i ] ][ x[ k ] ] + dis[ x[ k ] ][ x[ j ] ];
        for( int j = i; j <= n; ++j )
            for( int k = i; k <= n; ++k )
                if( dis[ x[ j ] ][ x[ k ] ] > dis[ x[ j ] ][ x[ i ] ] + dis[ x[ i ] ][ x[ k ] ] )
                    dis[ x[ j ] ][ x[ k ] ] = dis[ x[ j ] ][ x[ i ] ] + dis[ x[ i ] ][ x[ k ] ];
        for( int j = i; j <= n; ++j )
            for( int k = i; k <= n; ++k )
                ans[ i ] += dis[ x[ j ] ][ x[ k ] ];
    }
    for( int i = 1; i <= n; ++i )
        cout << ans[ i ] << ( i == n ? '\n' : ' ' );
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n;
    for( int i = 1; i <= n; ++i )
        for( int j = 1; j <= n; ++j )
            cin >> a[ i ][ j ];
    for( int i = 1; i <= n; ++i )
        cin >> x[ i ];
    solve();
    return 0;
}