Submission #66739952

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define ull unsigned long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define s second
#define f first
#define pb push_back
#define oo 1000000000000000000ll
#define all(a) (a).begin(), a.end()
#define rall(a) (a).rbegin(), a.rend()
#define mp make_pair

void calc(int u, int x, vector<vector<int>>& dp, vector<vector<pii>>& red){

    if (dp[u][x] != -1) return;

    dp[u][x] = 0;
    for (auto [from, w] : red[u]){
        calc(from, x ^ w, dp, red);
        if (dp[from][x ^ w]) dp[u][x] = 1;
    }

}

void solve() {
    int MX = (1 << 10);

    int n, m; cin >> n >> m;
    vector<vector<pii>> red(n+1);
    for (int i = 0; i < m; ++i){
        int a, b, w; cin >> a >> b >> w;
        red[b].pb({a, w});
    }

    vector<vector<int>> dp(n+1, vector<int>(MX, -1));
    dp[1][0] = 1;
    for (int i = 0; i < MX; ++i){
        calc(n, i, dp, red);
        if (dp[n][i]){
            cout << i << "\n";
            return;
        }
    }

    cout << "-1\n";

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tst; tst = 1;
    //cin >> tst;
    while (tst--){
        solve();
    }

    return 0;

}

Submission Info

Judge Result