Submission #66774680

---

Source Code Expand

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

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

    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // For undirected graphs
    }

    // `dis[node]` = min XOR to reach `node`
    vector<int> dis(n + 1, -1); // -1 means unvisited
    queue<pair<int, int>> q; // {current_xor, node}

    dis[1] = 0;
    q.push({0, 1});

    while (!q.empty()) {
        auto current_xor = q.front().first;
        int u = q.front().second;
        q.pop();

        for (auto child : adj[u]) {
        	int v = child.first;
        	int w = child.second;
            int new_xor = current_xor ^ w;
            if (dis[v] == -1 || new_xor < dis[v]) { // If unvisited or better XOR found
                dis[v] = new_xor;
                q.push({new_xor, v});
            }
        }
    }

    cout << dis[n] << endl; // -1 if no path exists
    return 0;
}

Submission Info

Judge Result