ABC 183 | C - Travel

問題

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

考えたこと

$2 \leq N \leq 8$なので単純に全列挙すればよい。

例えば$N=4$のときは以下のような配列を用意して青の部分を全列挙して移動時間の合計を加算し$K$と比較すればよい。

コード

実装時のTips

• 全列挙にはnext_permutationを使う。next_permutationは全列挙したい部分を指定できるので最初と最後のインデックスを除いてやれば青の部分だけ全列挙できる

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<vector<ll>> t(n, vector<ll>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> t[i][j];
    }
  }
  vector<ll> v;
  for (int i = 0; i < n; i++) {
    v.push_back(i);
  }
  v.push_back(0);
  ll ans = 0;
  do {
    ll tl = 0;
    for (int i = 0; i < v.size() - 1; i++) {
      tl += t[v[i]][v[i + 1]];
    }
    if (tl == k) {
      ans++;
    }
  } while (next_permutation(v.begin() + 1, v.end() - 1));
  cout << ans << endl;
}

参考

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