問題概要

$N$ 個の都市 $1, 2, \dots, N$ がある。都市 $i$ と都市 $j$ とは距離が $T_{i, j}$ だけ離れている。

都市 $1$ から出発して各都市をちょうど一度ずつ訪問して都市 $1$ に戻ってくる方法のうち、その移動距離の総和が $K$ となるものが何通りあるか、数え上げよ。

制約

$2 \le N \le 8$

解法 (1)：next_permutation

0-indexed で考えることにする。都市 0 から出発して、都市 0 に戻ってくる方法は、全部で $(N-1)!$ 通りある。 $N \le 8$ なので全探索で十分間に合いそうだ。

さて問題は、 $(N-1)!$ 通りのパターンをどのように全列挙するかということになる。たとえば $N = 4$ のときは、以下のパターンを全列挙したい。

0 -> (1 -> 2 -> 3) -> 0
0 -> (1 -> 3 -> 2) -> 0
0 -> (2 -> 1 -> 3) -> 0
0 -> (2 -> 3 -> 1) -> 0
0 -> (3 -> 1 -> 2) -> 0
0 -> (3 -> 2 -> 1) -> 0

実はこれは C++ なら、next_permutation というライブラリが用意されている。たとえば、v = (2, 1, 3) に対して

next_permutation(v.begin(), v.end());

とすると、v = (2, 3, 1) になるのだ。最終状態になったら next_permutation() が false を返すので、それを利用して探索を終了することができる。

コード

計算量は $O(N!)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;
    vector<vector<long long>> T(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> T[i][j];

    long long res = 0;
    vector<int> ids(N-1);
    for (int i = 0; i < N-1; ++i) ids[i] = i+1;
    do {
        long long dis = 0;
        int from = 0;
        for (int i = 0; i < ids.size(); ++i) {
            dis += T[from][ids[i]];
            from = ids[i];
        }
        dis += T[ids.back()][0];
        if (dis == K) ++res;

    } while (next_permutation(ids.begin(), ids.end()));
    cout << res << endl;
}

解法 (2)：再帰関数

再帰関数で実装することもできる。「すでに訪れた頂点」をビットで管理するといい感じ。

計算量は同じく $O(N!)$ となる。

#include <bits/stdc++.h>
using namespace std;

// 入力
long long N, K;
vector<vector<long long>> T;

// 返り値: 本数
// dist: これまでの道のり
// last: 直前に訪れた頂点
// visited: 訪れた頂点集合をビットで表したもの
int rec(long long dist = 0, int last = 0, int visited = (1<<0)) {
    // すべて訪問したら、頂点 0 に戻って距離が K なら 1 加算
    if (visited == (1<<N)-1) {
        dist += T[last][0];
        if (dist == K) return 1;
        else return 0;
    }

    int res = 0;
    for (int v = 1; v < N; ++v) {
        // すでに訪問済みの頂点はダメ
        if (visited & (1<<v)) continue;

        // 再帰的に探索
        res += rec(dist+T[last][v], v, visited|(1<<v));
    }
    return res;
}

int main() {
    cin >> N >> K;
    T.assign(N, vector<long long>(N, 0));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> T[i][j];
    cout << rec() << endl;
}