AtCoder Beginner Contest 183, C : Travel

問題文

　https://atcoder.jp/contests/abc183/tasks/abc183_c

問題概要

　$N$ 個の街があり，街 $i$ から街 $j$ へ移動するのにかかる時間は $T_{i,j}$ である．
　街 $1$ を出発して，街 $1$ 以外のすべての街を丁度一度ずつ訪問してから街 $1$ に戻ってくるルートであって，所要時間が丁度 $K$ になるものは何通りあるか？

制約

• $2 \leq N \leq 8$
• $1 \leq T_{i,j} \leq 10^8$
• $1 \leq K \leq 10^9$

解法

　この節では $0$-indexed で考えます．
　街の数が最大でも $8$ と少ないです．$8$ 個程度であれば，訪問する順序をすべて試すことができます．従って，std::next_permutation を使ってすべての順列を試し，所要時間が $K$ になるかを調べることで問題を解くことができます．
　実装のコツとしては，$v = \langle 0, 1, 2, \dots, n - 1, 0 \rangle$ な列を作って，begin( v ) + 1 と end( v ) - 1 の間に対して std::next_permutation をすると，始点と終点を固定したまま間の経路を全通り試せます．
　計算量としては，$O( N \times N! )$ になります．

コード

int main()
{
	IN( int, N, K );
	VVI T( N, VI( N ) );
	cin >> T;

	VI indices( N );
	iota( ALL( indices ), 0 );
	indices.PB( 0 );
	int res = 0;
	do
	{
		int k = 0;
		REP( i, N )
		{
			k += T[ indices[i] ][ indices[ i + 1 ] ];
		}
		res += k == K;
	}
	while ( next_permutation( begin( indices ) + 1, end( indices ) - 1 ) );

	cout << res << endl;

	return 0;
}