AtCoder Beginner Contest 183 C - Travel

問題

問題文へ

N個の都市があります。各都市間の移動時間が与えられます。

都市1を出発し、すべての都市をちょうど1度ずつ訪問して都市1へ戻る経路のうち、移動時間の合計がちょうどKになるものの個数を答えてください。

制約

• 
• 
• 
• 
• 
• 入力はすべて整数

考えたこと

都市の数が少ないので全探索できそうです。すべての順序はnext_permutationでがあります。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll N, K;
  cin >> N >> K;
  vector<vector<ll>> T(N, vector<ll>(N, 0));
  rep(i, N) rep(j, N) cin >> T[i][j];

  if (N == 2) {
    if (K == T[0][1] + T[1][0]) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }


  ll ans = 0;
  vector<int> perm;
  for (int i = 1; i < N; ++i) {
    perm.push_back(i);
  }

  do {
    ll time = 0;
    time += T[0][perm.front()];
    rep(i, perm.size() - 1) {
      time += T[perm[i]][perm[i + 1]];
    }
    time += T[perm.back()][0];
    if (time == K) ++ans;
  } while (next_permutation(perm.begin(), perm.end()));

  cout << ans << endl;
  
  return 0;
}

解説を読んで

C問題ならば答えられるようになってきましたが、細部が違います。

next_permutation(index.begin()+1, index.end());の部分がクールです。与えられる都市が2つの時に場合分けをしましたが必要ないようです。