Given a graph G = (V, E) with 1 <= N <= 100000 vertices and 1 <= M <= 100000 edges, how can I compute the minimum weighted path from vertex 1 to vertex N, where "weight" is defined as the exclusive bitwise XOR of all the edge weights?
For example if there is a graph with four vertices (call them 1, 2, 3) and 2 edges: one edge from 1 to 2 with weight 26, another edge from 2 to 3 with weight 18, then there's only one path from 1 to 3, so answer is 26 XOR 18 = 8.
I don't think most SSSP algorithms work here because XOR does not satisfy the triangle inequality. I was wondering whether anyone knows how to approach this problem.