[AtCoder] ABC 183 C – Travel

2020年11月15日2020年12月12日

問題

方針

\( N \) 個の順列の中で先頭が \( 1 \) であるものを探索します。したがって、順列を生成して全探索します。

コード

next_permutation

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

int main() {
    int N;
    ll K;
    cin >> N >> K;
    ll T[N][N];
    int v[N - 1];
    for (int i = 0; i < N; i++) {
        v[i] = i;
        for (int j = 0; j < N; j++) {
            cin >> T[i][j];
        }
    }
    int cnt = 0;
    do {
        ll t = 0;
        for (int i = 0; i < N - 1; i++) {
            t += T[v[i]][v[i + 1]];
        }
        t += T[v[N - 1]][v[0]];
        if (t == K && v[0] == 0) cnt++;
    } while (next_permutation(v, v + N));
    cout << cnt << "\n";
    return 0;
}

ライブラリなし

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

int cnt = 0;
int N, K;
int a[9]{}, flag[9]{};
int T[9][9]{};

void check() {
    int t = 0;
    for (int i = 0; i < N; i++) {
        t += T[a[i]][a[i + 1]]; // a[N] = 0
    }
    if (t == K) cnt++;
}

void solve(int n) {
    if (n == N) {
        check();
        return;
    }
    for (int i = 1; i < N; i++) {
        if (flag[i]) continue;
        a[n] = i;
        flag[i] = 1;
        solve(n + 1);
        flag[i] = 0;
    }
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> T[i][j];
        }
    }
    a[0] = 0;
    flag[0] = 1;
    solve(1);
    cout << cnt << "\n";
    return 0;
}