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.
Is the path allowed to visit some vertices/edges multiple times?
You can just use dfs, because all values in the original problem are < 1024. This should be sufficient to pass the first two subtasks.
First two subtasks? Where is this from?
This is basically a subtask of a problem from an active contest. The contest is not important by any means, but it's funny to see an account created an hour ago asking such a specific question.
This is exactly the same problem in a past edu round: 845G - Shortest Path Problem?
(The path is allowed to be not simple in this problem.)