巡回セールスマン問題

Traveling Salesman Problem | Aizu Online Judge

• 蟻本にものっていたやつ。
• bit DP を使う。

class traveling_salesman_problem {
public:
    // O(2^V*V^2)
    void solve(void) {
        const int inf = (1<<30);
        int V, E;
        cin>>V>>E;
        vector<vector<pair<int,int>>> tree(V);
        REP(i, E)
        {
            int s, t, d;
            cin>>s>>t>>d;
            // dp を簡単にするため t <- s なるように登録しておく
            tree[t].emplace_back(s,d);
        }
        // bit DP でやる
        // dp[unvisited][v] := 未到達頂点が unvisited で現在位置が v のときの残りの頂点を
        //                     全て巡回するための最小巡回コスト
        //
        vector<vector<ll>> dp((1<<V), vector<ll>(V, inf));

        // 頂点 0 からスタートして全部巡回させる
        dp[(1<<V)-1][0] = 0;
        // 0 頂点を除いた全ビットからスタート
        for (int unvisited = (1<<V)-2; unvisited >= 0; --unvisited)
        {
            // v in S な v 毎に回る
            for (int v = 0; v < V; ++v)
            {
                for (const auto &e : tree[v])
                {
                    int from, cost;
                    tie(from, cost) = e;
                    if ( ! (unvisited & (1<<from)) )
                        dp[unvisited][v] = min(dp[unvisited][v], dp[unvisited|(1<<from)][from] + cost);
                }
            }
        }
        int ans = dp[0][0];
        if (ans == inf)
            ans = -1;
        cout<<ans<<endl;
    }
};