全ての都市をそれぞれ1回は訪れる最小コスト（始点と終点は違ってよい, bit DP）を関数化した

• Quiz
  • E-Magical Ornament
  • https://atcoder.jp/contests/abc190/tasks/abc190_e
• AC
  • https://atcoder.jp/contests/abc190/submissions/19830501
• 感想
  • 似たのが来たら貼るぞ！
  • 距離行列やdpテーブルで未記入の-1やinfが混乱しがち
  • 訪れたらフラグを上げるのか下げるのか意識する
  • 開始位置に戻る/戻らないの違いはほぼない。戻らなくていいなら開始位置のフラグを最初から立てておくだけ

// G 距離行列
// G[i][j]==-1なら道なしとする
// グラフが連結であるかどうか
bool is_connected(VV& G){
  ll N = G.size();
  dsu uf(N);
  rep(i,N){
    FOR(j,i+1,N){
      if(G[i][j]>=0)uf.merge(i,j);
    }
  }
  return uf.groups().size()==1;
}

// 全ての都市（頂点）をそれぞれ1度は訪れるための最小移動距離（始点に戻る必要なし）
// G : 距離行列 (-1なら道なしとする)
// (N : 頂点数)
// bitDPを使うので計算量 N^2 x 2^N
// 到達不可能ならinfを返します
ll visit_all_city(VV& G){
  if(!is_connected(G)){
    debug("グラフが連結でないので全てを訪れることはできません");
    return inf;
  }
  ll N = G.size();
  // dp[i][j]
  // i : 訪れた都市のフラグ
  // j : 現在位置
  VV dp(1LL<<N, VI(N, -1)); // -1 : not assigned yet

  // メモ化再帰
  // f : 現在訪れた箇所はフラグ1とした訪問状態
  // now : 現在地
  function<ll(ll,ll)> rec = [&](ll f, ll now){
    if(dp[f][now]!=-1) return dp[f][now];
    // 次、どこに行こうかな
    ll mi = inf;
    rep(i, N){
      if(f>>i&1)continue; // already visited
      if(G[now][i]==-1)continue; // 道なし
      ll d = G[now][i] + rec(f|1LL<<i, i);
      chmin(mi, d);
    }
    return dp[f][now] = mi;
  };

  // 全てを訪れたならそこからの移動距離は0
  ll all = (1LL<<N)-1;
  rep(i,N){
    dp[all][i]=0;
  }
  ll mi = inf;
  rep(i,N){
    chmin(mi, rec(1LL<<i, i));
  }
  return mi;
}