Submission #66759095

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
using vp = vector<P>;
using vvp = vector<vector<P>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
using vp = vector<P>;
using vvp = vector<vector<P>>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

bool comp(const P a, const P b) {
    return a.second > b.second;
}

class Exiter {
    public:
    Exiter() {}
};
Exiter gram_dispersion = {};
    
template <class CharT>
[[noreturn]] void operator<<(std::basic_ostream<CharT> &stream, Exiter _exiter) {
    stream << std::endl;
    std::exit(0);
}

const ll MOD = 998244353;
const ll INF = 8e18;


const int MAX_BIT = 20;

struct XORB {
    ll basis[MAX_BIT] = {};

    void insert(ll x) {
        REPR(i, MAX_BIT) {
            if (!(x >> i & 1)) continue;
            if (!basis[i]) {
                basis[i] = x;
                return;
            }
            x ^= basis[i];
        }
    }

    ll minimize(ll x) {
        REPR(i, MAX_BIT) {
            if (basis[i] && (x ^ basis[i]) < x) {
                x ^= basis[i];
            }
        }
        return x;
    }
};

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    
    ll n, m;
    cin >> n >> m;
    ll a, b, w;
    vvp g(n);
    REP(i, m) {
        cin >> a >> b >> w;
        a--, b--;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    vll dist(n, -1);

    XORB basis;

    auto dfs = [&](auto self, ll v, ll d) -> void {
        dist[v] = d;
        for (auto [u, w] : g[v]) {
            if (dist[u] == -1) {
                self(self, u, d ^ w);
            } else {
                ll cycle = d ^ w ^ dist[u];
                if (cycle != 0) basis.insert(cycle);
            }
        }
    };
    dfs(dfs, 0, 0);

    ll res = dist[n - 1];
    if (res != -1) res = basis.minimize(res);
    cout << res << endl;
    return 0;
}

Submission Info

Judge Result