记录编号	600473	评测结果	AAAAAAAAAA
题目名称	[WC 2011] 最大异或和路径	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2025-05-04 17:51:04	内存使用	2.55 MiB

#include <cstdio>
typedef long long ll;

const int MAX_BIT = 64;
const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;

struct EDGE {
	int v, next;
	ll w;
} edge[MAXM << 1];

int head[MAXN], edgeNum;
void AddEdge(int u, int v, ll w) {
	edgeNum++;
	edge[edgeNum].v = v;
	edge[edgeNum].next = head[u];
	edge[edgeNum].w = w;
	head[u] = edgeNum;
}

ll basis[MAX_BIT]; 
void Insert(ll x) {
	for (int i = MAX_BIT - 1; i >= 0; --i) {
		if ((x >> i) & 1) {
			if (basis[i] == 0) {
				basis[i] = x;
				return ;
			}
			x ^= basis[i]; 
		}
	}
}

bool vis[MAXN];
ll xorsum[MAXN];
void dfs(int now) {
	vis[now] = 1;
	for (int i = head[now]; i; i = edge[i].next) {
		int v = edge[i].v;
		if (vis[edge[i].v]) {
			Insert(xorsum[now] ^ xorsum[v] ^ edge[i].w);
		} else {
			xorsum[v] = xorsum[now] ^ edge[i].w;
			dfs(v);
		}
	}
}

int n, m; 
ll ans;

int main() {
	freopen("xorr.in", "r", stdin);
	freopen("xorr.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v; ll w;
		scanf("%d %d %lld", &u, &v, &w);
		AddEdge(u, v, w);
		AddEdge(v, u, w);
	}
	dfs(1);
	ans = xorsum[n];
	for (int i = MAX_BIT - 1; i >= 0; --i) {
		if (((ans >> i) & 1) == 0 && basis[i]) {
			ans ^= basis[i];
		}
	} 
	printf("%lld", ans); 
	return 0;
}