状圧の説明部分はブログ状圧 DP 詳解（ビット演算）を参考にしています。
一、状圧 dp とは？#
ここは引用です
状圧 dp とは、状態を 2 進数に圧縮して保存することで、例えば行列の中で一行の状態を一つの二進数の文字列に圧縮することです。dp [S][v] の中で、S は既に訪れた頂点の集合を表し、v は現在の頂点を v とします。S が表すのは一つの状態（二進数表現）で、(11001)~2~ は二進数で {0，3，4} の 3 つの頂点が既に訪れたことを表し、(11001)~2~ が表す十進数は 25 です。したがって、S が 25 のときは実際には {0，3，4} の 3 つの頂点が既に訪れたことを示します。もし合計で 5 つの頂点（番号が 01234）ある場合、すべての頂点を訪問したことになります。Sj は (11111)~2~ です。
二、よく使うビット演算#
上記のいくつかの操作の例を示します。
例えば上記の (11001)~2~ は既に 0，3，4 の 3 つの頂点を訪れたことを示しています。次に頂点 2 を訪れる場合、以下の操作が可能です：1. 第 3 位は何ですか？つまり、二進数 x の第 k 位を取り出すことを選択します。y = x >>(k-1) & 1、y = (110)~2~ & 1 = 0、2. 第 3 位を 1 に変更します。y = x | (1<<(k-1))、y = (11001)~2~ | (100)~2~ = (11101)~2~、したがって頂点 2 の訪問が完了し、集合 S に追加され、終了しました。この時 S は (11101) 2 = 29 です。
三、例題#
A-Hie with the Pie#
問題の意図#
すべての地点間の往復に必要な時間（往復時間は異なる場合があります）を与えられ、最短時間で全ての地点の注文を配達し、ピザ店（番号 0）に戻る方法を求めます。
思考#
まず Floyd アルゴリズムを使用して最短経路行列を得ます。S を状態とし、dp [S][i] は i 番目の地点に到達するために必要な最短時間を示します。S から現在どの都市が配達されたかを知ることができ、S = 1<<N-1 はすべての地点が配達された状態です（N ビット全てが 1）。
コード#
// A-Hie with the Pie
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int inf = 0x3f3f3f;
int N,S,ans;
int dis[maxn][maxn];
int dp[1<<maxn][maxn];
void Floyd() {
for(int k = 0; k <= N; ++k) {
for(int i = 0; i <= N; ++i) {
for(int j = 0; j <= N; ++j) {
if(dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
int main(){
while(scanf("%d", &N) && N) {
for(int i = 0; i <= N; ++i) {
for(int j = 0; j <= N; ++j) {
scanf("%d", &dis[i][j]);
}
}
Floyd();
for(int S = 0; S < (1<<N); ++S) {//Sのすべての状態
for(int i = 1; i <= N; ++i) {//すべての配達地点
if(S & ( 1<<(i-1) )) { //地点iに配達する場合
if(S == ( 1<<(i-1) )) {//もしSがまだどの地点にも配達されていない場合
dp[S][i] = dis[0][i];
break;
} else {
dp[S][i] = inf;
for(int j = 1; j <= N; ++j) {
if(j == i) continue;
//現在の配達地点を除く、すでに配達された地点を列挙し、時間が短いかどうかを確認します
if(S&( 1<<(j-1) )) {
dp[S][i] = min(dp[S][i],dp[S^(1<<(i-1))][j] + dis[j][i]);
}
}
}
}
}
}
ans = inf;
for(int i = 1; i <= N; ++i) {
ans = min(ans, dp[(1<<N)-1][i] + dis[i][0]);
}
printf("%d\n",ans);
}
return 0;
}
B - Travelling#
問題の意図#
N 個の都市と M 本の道路コストが与えられ、Acmer 氏はすべての都市に行き、各都市には最大 2 回訪れることを希望します。必要な最低費用を求め、もしそのようなルートが見つからない場合は - 1 を出力します。
思考#
三進数の状圧 dp を使用し、各位が 0 は訪れていない、1 は 1 回訪れた、2 は 2 回訪れたことを示します。ここで cnt [i][j] は i が三進数で右から j 位目を示し、three [i] は三進数の i 位の位重みで、three [i] は二進数の 1<<i に似ています。最後にすべて訪問され、各都市に 2 回を超えない場合は ans と比較します。
コード#
// B - Travelling
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int maxt = 59049;
const int inf = 0x3f3f3f;
int N,M,S,ans;
int three[maxn];//three[i]は三進数のi位の最大値、二進数の1<<iに似ています
int map[maxn][maxn];
int cnt[maxt][maxn];//cnt[i][j]はiが三進数で右からj位目を示します
int dp[maxt][maxn];//dp[i][j]はiの状態でj都市に行った後の総費用を示します
void init() {
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
map[i][j] = inf;
}
map[i][i] = 0;
}
}
int main(){
int x = 3;
three[0] = 0;
three[1] = 1;
for(int i = 2; i < maxn; ++i) {
three[i] = x;
x *= 3;
}
for(int i = 0; i < three[maxn-1]; ++i) {
int now = i;
for(int j = 1; j <= 10 && now; ++j) {
cnt[i][j] = now % 3;
now /= 3;
}
}
while(~scanf("%d %d", &N, &M)) {
init();
for(int i = 1; i <= M; ++i) {
int u,v,w;
scanf("%d %d %d", &u, &v, &w);
if(w < map[u][v]) {
map[u][v] = map[v][u] = w;
}
}
for(int i = 1; i <= N; ++i) {
dp[three[i]][i] = 0;
}
int ans = inf;
for(int S = 0; S < three[maxn-1]; ++S) {//Sのすべての状態
bool allvis = true;
for(int i = 1; i <= N; ++i) {//すべての都市を列挙
if(cnt[S][i] == 0) //この状態で訪れていない都市がある
allvis = false;
if(dp[S][i] == -1) continue;
for(int j = 1; j <= N; ++j) { //次に訪れることができる都市を列挙
if(i == j || map[i][j] == inf || cnt[S][j] >= 2)
continue;
int nS = S+three[j];//次の状態
if(dp[nS][j] == -1 || dp[S][i] + map[i][j] < dp[nS][j]) { //次の都市の総費用が小さい
dp[nS][j] = dp[S][i] + map[i][j];
}
}
}
if(allvis) {
for(int i = 1; i <= N; ++i) {
if(dp[S][i] != -1) {
ans = min(ans, dp[S][i]);
}
}
}
}
if(ans == inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}