結果

問題 No.2236 Lights Out On Simple Graph
ユーザー otamay6
提出日時 2023-03-03 22:37:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,557 bytes
コンパイル時間 2,352 ms
コンパイル使用メモリ 205,760 KB
最終ジャッジ日時 2025-02-11 03:23:42
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

vector<vector<int>> graph;
vector<int> c;
int n,m;
constexpr int MAX = 1e9;

int dfs_pattern(){
    int idx = n;
    REP(i,n) {
        if(c[i] == 1){
            idx = i;
            break;
        }
    }
    if (idx == n) return 0;
    // 黒い点を探索する
    vector<pair<int, int>> black;
    vector<bool> used(n, false);
    used[idx] = true;
    queue<pair<int, int>> que;
    que.push(pair<int,int>(idx, 0));
    while(que.size()){
        pair<int,int> p = que.front(); que.pop();
        int dist = p.second + 1;
        for(auto v: graph[p.first]) {
            if(used[v]) continue;
            used[v] = true;
            if(c[v] == 1 && v > idx) {
                black.push_back(pair<int,int>(v, dist));
            }
            que.push(pair<int,int>(v, dist));
        }
    }
    int res = MAX;
    for(auto p: black){
        c[idx] = 0;
        c[p.first] = 0;
        res = min(res, dfs_pattern() + p.second);
        c[idx] = 1;
        c[p.first] = 1;
    }
    return res;
}

int main(){
    cin>>n>>m;
    graph.resize(n);
    REP(i,m) {
        int a,b;
        cin>>a>>b;
        a--;b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    c.resize(n);
    REP(i,n) cin>>c[i];
    int ret = dfs_pattern();
    cout << (ret==MAX?-1:ret) << endl;
}
0