ABC 183 | C - Travel

1 min read

問題

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;
}

参考

Discussion

ログインするとコメントできます