是我喜欢的典题，直接秒掉！

· · 题解

蒟蒻的第一篇紫题题解qwq

你个【数据删除】，做了道这么水还这么典的紫也要被你拉出来炫耀吗？

前置知识：线性基

首先，做过P4151 [WC2011] 最大XOR和路径这题的人就会知道，无向图上一条 x 到 y 的异或路径一定可以用另一条 x 到 y 的异或路径异或上若干个环得到。

不过做过 P4151 的应该都会这题，不用看题解了吧……

不知道这个结论也没关系，我们感性理解一下：

考虑这两条路径上端点相同但路径完全不重叠的一个部分，设两个端点分别为 x' 和 y'。因为这是一张无向图，所以第二条路径上的边全都可以反过来走，这样，我们可以从 x' 出发走第一条路径上的边到 y'，再从 y' 出发走第二条路径上的边到 x，相当于我们走了一个环。

而异或有个美妙的性质就是自己异或自己会变成 0，这等价于一条路径走了偶数次之后相当于没走。所以我们走了一次第二条路径，就等价于我们走了一次这个环之后又走了一次第一条路径。

对于整条路径的其他部分也进行相同的考虑，我们不难得出上面的结论。

那么这个结论有什么用呢？

当我们确定了起点 x 后，对于每一个从 x 出发可以到达的点 y，我们只需要确定两点之间的一条路径，再将从 x 出发能到达的环的权值加入异或线性基，便可以轻松确定答案。

至于如何找出所有从 x 出发能到达的环……这个可以直接 dfs。具体地，我们在从 x 出发 dfs，如果在点 y 碰到了在当次 dfs 中已经走过的点 z，说明 x \rightarrow y \rightarrow z \rightarrow x 形成了一个环（毕竟这是无向图）。设 dis_{y} 为从 x 出发走到 y 的权值 （只更新一次），那么这个环的权值就是 dis_y \operatorname{xor} w_i \operatorname{xor} dis_z。（和 P4151 一样的处理方法）

那么这道紫题就被我们水灵灵地做完了~

#include <bits/stdc++.h>
#define N 500
#define M 20000
#define K 10
#define INF 114514
#define mod 1
#define int1 int
using namespace std;
int1 n,m,i,j,ans;
int1 xxj[K + 5];//xian xing ji，线性基（
int1 dis[N + 5];
int1 hea[N + 5],nex[M + 5],to[M + 5],w[M + 5],bs;
bool vis[N + 5];
// 快读部分已省略
void add_edge(const int1 x,const int1 y,const int1 z){//链式前向星建边
    nex[++bs] = hea[x],hea[x] = bs,to[bs] = y,w[bs] = z;
    return ;
}
void two_edge(const int1 x,const int1 y,const int1 z){//建双向边
    add_edge(x,y,z),add_edge(y,x,z);
    return ;
}
void insert(int1 x){
    for(int1 i = K; i >= 0; i--){
        if((x >> i) & 1){
            if(!xxj[i]){
                xxj[i] = x;
                return ;
            }
            x ^= xxj[i];
        }
    }
    return ;
}
void dfs(const int1 x,const int1 s){
    dis[x] = s,vis[x] = 1;
    for(int1 i = hea[x]; i; i = nex[i]){
        int1 y = to[i];
        if(!vis[y]){
            dfs(y,s ^ w[i]);
        }else{
            insert(s ^ w[i] ^ dis[y]);
        }
    }
    return ;
}
int main(){
    n = read(),m = read();
    for(i = 1; i <= m; i++){
        const int1 x = read(),y = read();
        two_edge(x,y,read());
    }
    ans = INF;
    for(int1 x = 1; x <= n; x++){//枚举起点
        for(i = 1; i <= n; i++){
            dis[i] = 0;
            vis[i] = 0;
        } 
        for(i = 0; i <= K; i++){
            xxj[i] = 0;
        }
        dfs(x,0);
        for(int1 y = 1; y <= n; y++){//枚举终点
            if(x == y || !vis[y]){//起点必须可达终点，且起点和终点不能相同
                continue;
            }
            int1 s = dis[y];
            for(i = K; i >= 0; i--){
                s = min(s,s ^ xxj[i]);
            }
            ans = min(ans,s);
        }
    }
    if(ans == INF){
        pe(-1);
        return 0;
    } 
    pe(ans);
    return 0;
}