### awang01999's blog

By awang01999, history, 13 months ago,

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.

• -17

 » 13 months ago, # |   0 Is the path allowed to visit some vertices/edges multiple times?
 » 13 months ago, # |   0 You can just use dfs, because all values in the original problem are < 1024. This should be sufficient to pass the first two subtasks.
•  » » 13 months ago, # ^ |   0 First two subtasks? Where is this from?
•  » » » 13 months ago, # ^ |   +29 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.
 » 13 months ago, # | ← Rev. 2 →   +13 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.)