この問題は bitDP により解くことができます。

\(\mathrm{DP}[S]\) を「まだ壊されていない建物の集合が \(S\) であるとき、これらを解体するのにかかる費用の最小値」とします。

どの建物から解体するかを考えることで

\(\mathrm{DP}[S]=\min_{x\in S}(\mathrm{DP}[S\setminus\{x\}] + C_x + \sum_{y \not \in S}W_{y,x})\)

となります。右辺は \(O(N^2)\) で計算できることから、 \(O(2^N N^2)\) でこの問題を解くことができました。

実装例 (C++)

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

int main(){
  int n;
  cin >> n;
  vector<int> c(n);
  for(int i=0; i<n; i++) cin >> c[i];
  vector<vector<int>> w(n, vector<int>(n));
  for(int i=0; i<n; i++)for(int j=0; j<n; j++) cin >> w[i][j];

  vector<long long> dp(1<<n, 1e18);
  dp[0] = 0;

  for(int s=1; s<1<<n; s++){
    for(int x=0; x<n; x++){
      if(!((s>>x)&1)){
        continue;
      }
      long long cost  = 0;
      for(int y=0; y<n; y++){
        if(!((s>>y)&1)){
          cost+=w[y][x];
        }
      }
      dp[s] = min(dp[s], dp[s^(1<<x)] + c[x] + cost);
    }
  }

  cout << dp.back() << endl;
}

実装例 (Python)

N = int(input())
C = list(map(int, input().split()))
W = [list(map(int, input().split())) for _ in range(N)]

dp = [10**18] * (1<<N)
dp[0] = 0

for s in range(1, 1<<N):
  for x in range(N):
    if not (s>>x)&1:
      continue
    dp[s] = min(dp[s], dp[s^(1<<x)] + C[x] + sum(W[y][x] for y in range(N) if not (s>>y)&1))

print(dp[-1])

おまけ

なお、\(f(S,x):=\sum_{y \not \in S}W_{y,x}\) を全ての \((S, x)\) に対して前計算しておくことで、DPの遷移式の \(O(2^N N)\) で計算できるようになります。
\(f(S,x)\) を定義通りに計算していると、\(O(2^NN^2)\) かかってしましますが、\(S\) の index 最小の要素を \(i\) として \(f(S.x)=f(S\setminus\{i\},x)+W_{i,x}\) と計算することで、\(f(S,x)\) は再帰的に 1 つあたり \(O(1)\)、全体で \(O(2^NN)\) で計算することができ、全体で O\((2^NN)\) でこの問題を解くことができます。