提出 #17477921

ソースコード 拡げる

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N; cin >> N;
  vector<ll> X(N, 0), Y(N, 0), Z(N, 0);
  for (ll i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> Z[i];
  }
  ll MAX = (1<<N);

  ll INF = 1e18;
  vector<ll> dp(MAX, INF);
  vector<ll> last(MAX, 0);
  ll ans = INF;

  dp[0] = 0;
  for (ll i = 0; i < MAX; i++) {
    if (dp[i] == INF) continue;
    for (ll j = 0; j < N; j++) {
      if (i & (1<<j)) continue;
      if ( (i|1<<j) == MAX - 1) {
        ll k = last[i];
        ll d = dp[i] + abs(X[j] - X[k]) + abs(Y[j] - Y[k]) + max(Z[j] - Z[k], 0ll);
        d += abs(0 - X[j]) + abs(0 - Y[j]) + max(0 - Z[j], 0ll);
        ans = min(ans, d);
      }
      ll k = last[i];
      ll d = abs(X[j] - X[k]) + abs(Y[j] - Y[k]) + max(Z[j] - Z[k], 0ll);
      if(dp[i|1<<j] > dp[i] + d) {
        dp[i|1<<j] = dp[i] + d;
        last[i|1<<j] = j;
      }
      d = abs(0 - X[k]) + abs(0 - Y[k]) + max(0 - Z[k], 0ll);
      d += abs(X[j] - 0) + abs(Y[j] - 0) + max(Z[j] - 0, 0ll);
      if(dp[i|1<<j] > dp[i] + d) {
        dp[i|1<<j] = dp[i] + d;
        last[i|1<<j] = j;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

提出情報

提出日時
問題 E - Traveling Salesman among Aerial Cities
ユーザ nakaken88
言語 C++ (GCC 9.2.1)
得点 0
コード長 1263 Byte
結果 WA
実行時間 33 ms
メモリ 5296 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 2
WA × 1
AC × 2
WA × 21
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random_01.txt WA 33 ms 5256 KiB
random_02.txt WA 2 ms 3552 KiB
random_03.txt WA 31 ms 5136 KiB
random_04.txt WA 28 ms 5200 KiB
random_05.txt WA 24 ms 5128 KiB
random_06.txt WA 2 ms 3608 KiB
random_07.txt WA 31 ms 5296 KiB
random_08.txt WA 6 ms 3552 KiB
random_09.txt WA 30 ms 5128 KiB
random_10.txt WA 2 ms 3632 KiB
random_11.txt WA 29 ms 5180 KiB
random_12.txt WA 2 ms 3504 KiB
random_13.txt WA 28 ms 5228 KiB
random_14.txt WA 2 ms 3436 KiB
random_15.txt WA 29 ms 5236 KiB
random_16.txt WA 4 ms 3612 KiB
random_17.txt WA 25 ms 5176 KiB
random_18.txt WA 4 ms 3732 KiB
random_19.txt WA 26 ms 5264 KiB
random_20.txt WA 9 ms 3548 KiB
sample_01.txt AC 2 ms 3608 KiB
sample_02.txt AC 2 ms 3604 KiB
sample_03.txt WA 27 ms 5296 KiB