Top

(ΦωΦ)＜これのつづきですよー。目次はここ。

---
有名なこれをやろう。
「巡回セールスマン問題」
$n$ 個の街と、街と街を結ぶ $m$ 個の道があります。道を通るにはコストがかかります。
ある街から出発し、すべての街をちょうど一度通って帰ってくるルートのうち、コストの和が最小になるものを選んだとき、
そのコストの和の最小値を求めてください。Aizu Online Judge "Traveling Salesman Problem"
$n$ は $15$ 以下。それぞれの道のコストは $1{,}000$ 以下。

「どの街を既に訪ねたか」と「今どの街にいるか」、この2つの状態でやってみよう。
どの街を既に訪ねたかというのは、1: 訪ねた, 0: まだ という $n$ ビットの情報にするのが定石で、
集合に対する演算をビット操作を駆使してやる(蟻本初版pp.143-145)。
とりあえず、
$n$ 個の要素からなる集合 $S$ の全ての部分集合 $T$for(int T=0; T<1<<n; T++)
集合 $S$ に $i$ 番目の要素を入れた(= $i$ 番の街を訪ねたことにする)集合S | 1<<i
集合 $S$ に $i$ 番目の要素が入ってるかどうか調べる(= $i$ 番の街を既に訪ねたかどうか調べる)if(S>>i & 1)
これだけは覚えておいて。

(ΦωΦ)＜メモ化再帰
#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 987654321;
int n, m;
vector<vector<int>> G;
vector<vector<int>> dp;

int rec(int mask, int v) {
  if(dp[mask][v] != -1) { return dp[mask][v]; }
  if(mask==(1<<n)-1 && v==0) { return dp[mask][v] = 0; }
  int res = inf;
  for(int i=0; i<n; i++) {
    if(mask>>i & 1) { continue; }
    // v番の街からi番の街に行く
    res = min(res, rec(mask|(1<<i), i) + G[v][i]);
  }
  return dp[mask][v] = res;
}

int main(void) {
  scanf("%d%d", &n, &m);
  G.assign(n, vector<int>(n, inf));
  for(int i=0; i<m; i++) {
    int p, q, c; scanf("%d%d%d", &p, &q, &c);
    G[p][q] = c;
  }
  dp.assign(1<<n, vector<int>(n, -1));
  int res = rec(0, 0);
  if(res >= inf) { res = -1; }
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜forループ
#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 987654321;

int main(void) {
  int n, m; scanf("%d%d", &n, &m);
  vector<vector<int>> G(n, vector<int>(n, inf)),
                      dp(1<<n, vector<int>(n, -1));
  for(int i=0; i<m; i++) {
    int p, q, c; scanf("%d%d%d", &p, &q, &c);
    G[p][q] = c;
  }
  dp[0][0] = 0;
  for(int mask=0; mask<1<<n; mask++) {
    for(int v=0; v<n; v++) {
      for(int i=0; i<n; i++) {
        if(mask>>i & 1) { continue; }
        int &a = dp[mask][v],
            &b = dp[mask|(1<<i)][i];
        if(a == -1) { a = inf; }
        if(b == -1) { b = inf; }
        b = min(b, a + G[v][i]);
      }
    }
  }
  int res = dp[(1<<n)-1][0];
  if(res >= inf) { res = -1; }
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜つづく