题面传送门 一道套路题。 考虑把图分解成链与环。 然后我们会发现其实路径就是一条链加上一堆环。 因为从链走到环的路径会被异或两次为 0 0 0 所以就直接上线性基就好了。 代码实现:
#include<cstdio> using namespace std; int n,m,k,x,y,flag[100039]; long long p[10039],z,ans,d[100039]; struct yyy{int to;long long w;int z;}; struct ljb{ int head,h[100039]; yyy f[200039]; inline void add(int x,int y,long long z){ f[++head]=(yyy){y,z,h[x]}; h[x]=head; } }s; inline void get(long long x){ int i; for(i=62;i>=0;i--) { if(x&(1ll<<i)){ if(!p[i]){p[i]=x;break;} x^=p[i]; } } } inline void dfs(int x,int last,long long pus){ if(x==n) ans=pus; d[x]=pus; flag[x]=1; int cur;yyy tmp; for(cur=s.h[x];cur;cur=tmp.z){ tmp=s.f[cur]; if(tmp.to!=last){ if(!flag[tmp.to]) dfs(tmp.to,x,pus^tmp.w); else get(pus^d[tmp.to]^tmp.w); } } } inline long long find(){ for(int i=62;i>=0;i--)if((ans^p[i])>ans) ans^=p[i]; return ans; } int main(){ register int i; scanf("%d%d",&n,&m); while(m--) scanf("%d%d%lld",&x,&y,&z),s.add(x,y,z),s.add(y,x,z); dfs(1,0,0); printf("%lld\n",find()); }