题意：给出一幅无向图，求1到n的所有路径中最大异或和，一条边可以被重复经过。
思路：
参考了大佬的博客
#pragma GCC optimize (2) #pragma G++ optimize (2) #pragma comment(linker, "/STACK:102400000,102400000") #include<bits/stdc++.h> #include<cstdio> #include<vector> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=100010; int n,m,vis[maxn]; struct edge{ int to; ll w; }; vector<edge >ve[maxn]; ll link,del[maxn]; ll p[70]; void insert(ll res){ dep(i,63,0){ if((res>>i)&1){ if(!p[i]){ p[i]=res; break; } res^=p[i]; } } } ll query(ll x){ dep(i,63,0){ if((x^p[i])>x){ x^=p[i]; } } return x; } void dfs(int u,ll res){ del[u]=res; vis[u]=1; if(u==n){ link=res; } for(auto &st:ve[u]){ if(vis[st.to]){ insert(res^st.w^del[st.to]); }else{ dfs(st.to,res^st.w); } } } int main(){ while(cin>>n>>m){ rep(i,1,n){ ve[i].clear(); vis[i]=0; } rep(i,1,m){ int u=rd(),v=rd(); ll w=rd(); ve[u].pb({v,w}),ve[v].pb({u,w}); } link=-1; dfs(1,0); printf("%lld\n",query(link)); } }