巡回セールスマン問題
概要
巡回セールスマン問題を動的計画法によって解きます．
使い方
dp[S][v] = u $\in$ S を全て訪れ v にいるときの最小値．
計算量
$O(E 2^V)$
実装
Weight travelingSalesman(const Graph &g) {
int n = g.size();
Matrix dp(1 << n, Array(n, inf));
dp[0][0] = 0;
for (int S = 0; S < 1 << n; S++) {
for (auto &es : g) {
for (auto &e : es) {
int u = e.src, v = e.dst;
auto w = e.weight;
if (~S >> v & 1) dp[S | 1 << v][v] = std::min(dp[S | 1 << v][v], dp[S][u] + w);
}
}
}
return dp[(1 << n) - 1][0];
}