巡回セールスマン問題

• Quiz
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
• AC
  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4878456#1
• 解説
  • bit DP
  • chokudai https://www.slideshare.net/chokudai/wap-atcoder4
• その他
  • 最初は再帰関数＆メモ化で書いたが、その後上記解説を読み、配るDPで書き直した
  • 始点に戻ってこれるかどうかをうまく判定することが重要

struct Edge{
    ll to;
    ll cost;
    Edge(ll to, ll cost): to(to), cost(cost) {}
    Edge(){
        to = 0;
        cost = 0;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    // 有向グラフ
    vector<vector<Edge>> G(N);

    rep(i,M){
      ll a,b,c;
      cin>>a>>b>>c;
      G[a].push_back({b,c});
    }

    // dp[flag][last]]
    VV dp(1<<N, VI(N, inf));
    auto reset_dp = [&](){
      rep(i,1<<N){
        rep(j,N){
          dp[i][j]=inf;
        }
      }
    };

    ll mi=inf;
    rep(start,N){
      reset_dp();
      dp[0][start]=0;
      rep(flags,1<<N){
        rep(lst,N){
          if(dp[flags][lst]==inf)continue;
          // 現在のフラグ＆最後の位置から遷移できるところに遷移（配るDP）する
          for(auto edge : G[lst]){
            ll to = edge.to;
            if((flags>>to&1)==0){
              // そこがまだ0（未踏）なら行ける
              ll new_flags = flags | (1<<to);
              ll new_dist = dp[flags][lst] + edge.cost;
              chmin(dp[new_flags][to], new_dist);
            }  
          }
        }
      }
      ll all = (1<<N)-1;
      if(dp[all][start]==inf)continue; // 始点に戻ってこれない場合
      chmin(mi,dp[all][start]);
    }

    if(mi==inf){
      p(-1);
    }else{
      p(mi);
    }
    
    return 0;
}