Submission #63594446

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

int ans = -1;

void dfs(int node, vector<bool>& vis, int Xor, vector<vector<int>>& adj, int n) {
    if (node == n) { // Reached the last node
        if (ans == -1) ans = Xor;
        else ans = min(ans, Xor);
        return;
    }
  
    for (int child = 1; child <= n; child++) {
        if (!vis[child] && adj[node][child] != -1) {
            vis[child] = true;
            dfs(child, vis, Xor ^ adj[node][child], adj, n);
            vis[child] = false; // Backtrack
        }
    }
}

signed main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n + 1, vector<int>(n + 1, -1));
    vector<bool> vis(n + 1, false);
  
    for (int i = 0; i < k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }
  
    vis[1] = true; 
    dfs(1, vis, 0, adj, n);
  
    cout << ans << endl;
}

Submission Info

Judge Result