結果
問題 |
No.943 取り調べ
|
ユーザー |
![]() |
提出日時 | 2019-12-31 18:55:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 228 ms / 1,206 ms |
コード長 | 1,623 bytes |
コンパイル時間 | 1,873 ms |
コンパイル使用メモリ | 172,220 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-19 15:14:08 |
合計ジャッジ時間 | 4,082 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long int; using ull = unsigned long long int; using P = pair<int, int>; using P3 = pair<ll,P>; using PP = pair<P ,P>; constexpr ll MOD = 998244353; constexpr int IINF = INT_MAX; constexpr ll LLINF = LLONG_MAX; constexpr int MAX_N = int(1e6) + 5; constexpr double EPS = 1e-8; constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0}; #define REP(i, n) for (int i = 0; i < n; i++) #define REPR(i, n) for (int i = n; i >= 0; i--) #define SORT(v) sort((v).begin(), (v).end()) #define SORTR(v) sort((v).rbegin(), (v).rend()) #define ALL(v) (v).begin(), (v).end() int main(){ int n; cin >> n; vector<vector<int> > x(n, vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin >> x[i][j]; } } vector<int> a(n); for(int i=0;i<n;i++){ cin >> a[i]; } int ans = IINF; for(int S=0;S<1<<n;S++){ int T = 0; bool update = true; while(update){ update = false; for(int i=0;i<n;i++){ if((T>>i)&1) continue; bool ok = true; for(int j=0;j<n;j++){ ok &= x[i][j]==0 || ((T>>j)&1) || ((S>>j)&1); } if(ok){ T |= 1<<i; update = true; } } } if(T == (1<<n)-1){ int cost = 0; for(int i=0;i<n;i++){ if((S>>i)&1) cost += a[i]; } ans = min(ans, cost); } } cout << ans << endl; return 0; }