awang01999's blog

By awang01999, history, 4 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the path allowed to visit some vertices/edges multiple times?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can just use dfs, because all values in the original problem are < 1024. This should be sufficient to pass the first two subtasks.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First two subtasks? Where is this from?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

This is exactly the same problem in a past edu round: 845G - Кратчайший путь?

(The path is allowed to be not simple in this problem.)