提出 #65483572

---

ソースコード 拡げる

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

using ll = long long;

int main() {
  // 入力を受け取る
  int N, M;
  cin >> N >> M;
  vector<ll> C(N), K(M);
  vector<vector<int>> A(M);
  for(int i = 0; i < N; i++) {
    cin >> C[i];
  }
  for(int i = 0; i < M; i++) {
    cin >> K[i];
    A[i].resize(K[i]);
    for(int j = 0; j < K[i]; j++) {
      cin >> A[i][j];
    }
  }

  // can_see[i] := (動物園 i で見ることができる動物のリスト)
  vector<vector<int>> can_see(N);
  for(int i = 0; i < M; i++) {
    for(int j = 0; j < K[i]; j++) {
      can_see[A[i][j] - 1].push_back(i);
    }
  }

  // bit 全探索のさらに bit 全探索をする
  ll ans = 2'000'000'000'0;
  for(int s = 0; s < 1 << N; s++) {
    for(int t = s; t >= 0; t--) {
      t &= s;
      ll cost = 0;
      vector<int> cnt_vis(N);
      vector<int> cnt_see(M);
      for(int i = 0; i < N; i++) {
        cnt_vis[i] += (s >> i) & 1;
        cnt_vis[i] += (t >> i) & 1;
        cost += cnt_vis[i] * C[i];
        for(int animal : can_see[i]) cnt_see[animal] += cnt_vis[i];
      }
      bool ok = true;
      for(int i = 0; i < M; i++) {
        if(cnt_see[i] < 2) ok = false;
      }
      if(ok) ans = min(ans, cost);
    }
  }
  
  cout << ans << endl;
}

提出情報

ジャッジ結果