Submission #66759824

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>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> g(n);
    rep(i, m) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].emplace_back(b, w);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> g(n);
    rep(i, m) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].emplace_back(b, w);
    }

    const ll INF = LLONG_MAX;
    vector<ll> dist(n, INF);
    vector<ll> basis(60, 0);

    dist[0] = 0;
    queue<int> que;
    que.push(0);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto [v, w] : g[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] ^ w;
                que.push(v);
            } else {
                ll x = dist[u] ^ w ^ dist[v];
                for (int bit = 59; bit >= 0; --bit) {
                    if (!(x >> bit & 1)) continue;
                    if (!basis[bit]) {
                        basis[bit] = x;
                        break;
                    }
                    x ^= basis[bit];
                }
            }
        }
    }

    ll res = dist[n - 1];
    if (res == INF) {
        cout << -1 << "\n";
        return 0;
    }
    for (int bit = 59; bit >= 0; --bit) {
        res = min(res, res ^ basis[bit]);
    }
    cout << res << "\n";
    return 0;
}

Submission Info

Judge Result