巡回セールスマン問題

問題

全頂点を訪れてた後、最初に戻る場合と戻らない場合がある(yが必要)

有向性グラフであり、矢印がない頂点間はINFを与える

ll N, E, y; //頂点、辺、最後に通る点
ll G[20][20];  // グラフ
ll dp[(1 << 20) + 1][21]; // dpテーブルは余裕をもったサイズにする


/* メモ化再帰 */
ll rec(int bit, ll v)
{
    
    // すでに探索済みだったらリターン
    // dp[bit][v]は一度で全パターン試されるので次呼ばれるときは計算不要
    // yが違う時(一周)の時は使えない
    //if (dp[bit][v] != -1) return dp[bit][v];

    
    // 初期値 (v(最後に訪れた頂点)だけが1(探索済み))
    if (bit == (1 << v)) {

        return dp[bit][v] = G[y][v]; //yが同じ時、dp[bit][v]は1通りしかない

    }
    
    ll res = INF; // 最短距離

    int prev_bit = bit &~ (1 << v); // ｖを探索済みに変える( &~ は Nand )


    for (ll u = 0; u < N; ++u) {
        if ((prev_bit & (1 << u)) == 0) continue; // u が探索済みなら
        
        // 階数ごとに最小値を求める
        if (res > rec(prev_bit, u) + G[u][v]) {
            res = rec(prev_bit, u) + G[u][v];
                    
        }
    }

    return dp[bit][v] = res; // メモしながらリターン
}


int main()
{
    // 入力
    cin >> N >> E;

    // グラフの初期化
    rep(i,0, 20) {
        rep(j,0, 20) { G[i][j] = INF; }
    }
    rep(i,0, E) {
        ll s, t, d;
        cin >> s >> t >> d;
        G[s][t] = d;
       
    }

    // テーブルを全部 -1 にしておく (-1 でなかったところは探索済)
    for (int bit = 0; bit < (1 << N); ++bit) for (ll v = 0; v < N; ++v) dp[bit][v] = -1;

    // 探索
    ll res = INF;
    for (ll v = 0; v < N; ++v) { // y は最後に通る頂点
        y = v;
        
        if (res > rec((1 << N) - 1, v)) {
            res = rec((1 << N) - 1, v); // 1が探索済み(逆から探索)
        }
    }

    if (res >= INF) cout << -1 << endl;
    else cout << res << endl;
    
}