問題概要
$n$ 頂点 $m $ 辺からなる重み付き単純有向グラフ $G = ( V = \{ 1, 2, \dots, n \}, E )$ がある．$i$ 番目の辺は $( U_i, V_i ) \in E$ であり，その重みは $w( ( U_i, V_i ) )$ である*1．関数 $w$ の値は負にもなり得るが，$G$ に負閉路は存在しない．
$G$ について，全ての頂点を含む「ウォーク」が存在するかどうか判定し，存在する場合はその（辺の）重みの和の最小値を求めよ．存在しない場合はそのことを報告せよ．「ウォーク」の詳細については原文参照のこと．
制約
- $2 \leq n \leq 20$
- $1 \leq m \leq n ( n - 1 )$
解法
前提知識というかなんと言いますか，問題名にも（部分的に）含まれる「巡回セールスマン問題」(TSP: Traveling Salesman Problem) については多少知っている必要があります*2．負辺を含まない場合の解法として，次のように状態をとる動的計画法が（いわゆる「bit DP」の例として？）競技プログラミング文脈でも知られています [1]：
\begin{align*}
\mathit{ dp }[S][u] = &\text{頂点集合 $S$ に含まれる頂点に訪問済みで，}\\ &\text{現在地が頂点 $u \in S$ である状態に到達する最小コスト}
\end{align*}
この DP で，状態 $\mathit{ dp }[S][u]$ からの遷移は，$v \not \in S$ なる辺 $( u, v ) \in E$ それぞれについて，$$\mathit{ dp }[ S \cup \{ v \} ][v] \overset{\mathrm{ chmin }}{\leftarrow} \mathit{ dp }[S][u] + w( ( u, v ) )$$ と更新します（$\overset{\mathrm{ chmin }}{\leftarrow}$ で，左辺を両オペランドの内大きくない方で更新する操作を表すことにします）．全ての更新を回し終わったあと，全頂点を訪問し終わった状態に到達するコストの最小値 $$\min_{ u \in V } \mathit{ dp }[V][u]$$ が答えです．詳細は省きますがこの DP は $\Theta( 2^n n )$ 空間・$O( 2 ^ n n ^2 )$ 時間で動作し，今回の問題に対して適用しても TLE しない程度となっています．
「じゃあ問題が解けたじゃないか」と一瞬思ってしまいますが，上記のアルゴリズムは負辺があると正しく動作しません．遷移先の頂点を試すループを回すときに，$S$ の大きさ $|S|$ が変化しないような遷移は（特に $2$ 歩以上動くとき）きちんとカバーされていないので，ウォークの辺数が $n - 1$ になることを暗に仮定しています．ところが今回の問題では，訪問済みの頂点に迂回した方がトータルのコストが少なくなるような移動が考えられるので，正しく解を求められません*3．逆に言えば，そういった移動を正しくハンドルできれば問題を解けます．
ところで，負閉路が存在しないということは，$\mathit{ dp }[S][u]$ の状態から $S$ を変化させずに，かつ $\mathit{ dp }[S][u]$ の値も更新しないように移動できる回数は高々 $n - 1$ 回です（そうでなければ負閉路ができてしまう）．よって，$u, v$ を試すループを $n - 1$ 回程度繰り返すと一応解けますが，何やら危なっかしい感じの時間がかかっています．計算量について考えてみると $O( 2^n n^3 )$ 時間となっているわけですが，これを改善したいです．
どこに無駄があるかと言えば，頂点 $u \in S$ から頂点 $v \not \in S$ への移動について $\Theta( n )$ 時間もかけて計算していることです．$2$ 点 $u, v$ の組合せ全てについて $u$ から $v$ への最適な移動方法（のコスト）を前もって計算できれば高速化が見込めます．これは「全点対最短経路問題」などと呼ばれるもので，解法として Floyd-Warshall 法が知られています．これを利用すると，先程のアルゴリズムは，
- Floyd-Warshall 法で全点間の最短距離を求める（$u$ から $v$ への最短距離を $W_{ u, v }$ とする）
- 前述の DP で更新をするとき，$w( ( u, v ) )$ の代わりに $W_{ u, v }$ を使う
とすることで改善できます．これで，Floyd-Warshall に時間がかかるようになる代わりに DP の計算量が落ちて全体で $O( n^3 + 2^n n^2 )$ 時間となり，安心して通せるようになります．「$u$ から $v$ への最短路を通るときに $S$ と矛盾する頂点を通るんじゃないか」という話については，$S$ の解釈を「確実に訪問した頂点の集合」と解釈し直すと大丈夫になります．
参考文献
[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. プログラミングコンテストチャレンジブック: 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える. マイナビ出版, 2012.
コード
constexpr auto INF = LIM<>::max() / 2; int main() { IN( int, N, M ); VI U( M ), V( M ), W( M ); REP( i, M ) { cin >> U[i] >> V[i] >> W[i]; --U[i], --V[i]; } VVI G( N, VI( N, INF ) ); REP( i, N ) { G[i][i] = 0; } REP( i, M ) { G[ U[i] ][ V[i] ] = W[i]; } REP( k, N ) { REP( i, N ) { REP( j, N ) { chmin( G[i][j], G[i][k] + G[k][j] ); } } } static int dp[ 1 << 20 ][ 32 ]; fill( AALL( dp ), INF ); REP( u, N ) { dp[ 1 << u ][u] = 0; } REP( s, 1 << N ) { REP( u, N ) { if ( !( s & 1 << u ) || dp[s][u] == INF ) { continue; } REP( v, N ) { if ( G[u][v] != INF ) { chmin( dp[ s | 1 << v ][v], dp[s][u] + G[u][v] ); } } } } int res = INF; REP( u, N ) { chmin( res, dp[ ( 1 << N ) - 1 ][u] ); } if ( res == INF ) { cout << "No" << endl; } else { cout << res << endl; } return 0; }
