Description

直接看标题就行

Solution

Xor这种东西，一般就是Trie或者线性基，这个题是线性基。

每个环都可以走到，而且来回的路上不会产生额外的代价，所以为每个环的Xor和建立线性基。算答案的时候随便选一条从1到n的路径就行，因为如果有其他路径，这两条路径一定成环，在线性基里求最值的时候就知道走那个更优了。

Code

#include 
    
     typedef long long LL;const int B = 62;const int N = 50010;const int M = 200010;int hd[N], nxt[M], to[M], cnt, n, m, vis[N];LL w[M], del[N];LL Lb[B];void ins(LL x) {    // printf("%I64d\n", x);    for (int i = 60; i>=0; --i) {        if (!(x>>i) & 1) continue;        if (!Lb[i]) {            Lb[i] = x;            break;        } else x ^= Lb[i];    }}LL query(LL x) {    for (int i = 60; i >= 0; --i) {        if (x < (x^Lb[i])) x ^= Lb[i];    }    return x;}void dfs(int x, LL res) {    vis[x] = 1; del[x] = res;    for (int i = hd[x]; i; i = nxt[i])        if (vis[to[i]]) ins(res^w[i]^del[to[i]]);        else dfs(to[i], res^w[i]);  }inline void adde(int x, int y, LL z) {    to[++cnt] = y;    nxt[cnt] = hd[x]; w[cnt] = z;    hd[x] = cnt;}int main() {    scanf("%d%d", &n, &m);    int x, y; LL z;    for (int i = 1; i <= m; ++i) {        scanf("%d%d%lld", &x, &y, &z);        adde(x, y, z);        adde(y, x, z);    }    dfs(1, 0);    printf("%lld\n", query(del[n]));    return 0;}