提出 #66354866

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0; i < (int)(n); ++i)
#define FOR(i, l, r)  for(int i = (int)(l); i < (int)(r); ++i)
#define RREP(i, n)    for(int i = (int)(n); i-- > 0;)
#define RFOR(i, r, l) for(int i = (int)(r); i-- > (int)(l);)
#define ALL(v)        std::begin(v), std::end(v)
using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int, int>;
using namespace std;
constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9 + 7;

template <typename Type>
inline std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
    for(auto &elem : v) is >> elem;
    return is;
}

template <typename Type>
inline std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
    for(auto iter = v.cbegin(); iter != v.cend(); ++iter) os << (iter == v.cbegin() ? "" : " ") << *iter;
    return os;
}

#ifdef DEBUG

#include "debug.hpp"

#else

#define debug(...) static_cast<void>(0)

#endif

int main(){
    int n,m;
    cin>>n>>m;

    vector g(n,vector<pii>());
    REP(i,m){
        int u,v;
        int w;
        cin>>u>>v>>w;
        u--, v--;

        g[u].emplace_back(v,w);
        g[v].emplace_back(u,w);
    }

    int ans=0;
    auto f=[&](int i)->bool{
        int mask=~((1<<i)-1);
        int want=ans&mask;
        debug(i,bitset<30>(mask));
        debug(i,bitset<30>(want));

        queue<int> que;
        que.push(0);
        vector<bool> seen(n,false);
        while(!que.empty()){
            auto u=que.front();
            que.pop();
            if(seen[u]) continue;
            seen[u]=true;

            for(auto [v,w]:g[u]){
                if((((w&mask)^want)|want)==want) que.push(v);
            }
        }

        return seen[n-1];
    };
    RREP(i,30){
        if(!f(i)) ans|=1<<i;
    }

    cout<<ans<<endl;
}

提出情報

ジャッジ結果